| 000 -LEADER |
|---|
| fixed length control field |
05387nam a2200769 i 4500 |
| 001 - CONTROL NUMBER |
|---|
| control field |
6813010 |
| 003 - CONTROL NUMBER IDENTIFIER |
|---|
| control field |
IEEE |
| 005 - DATE AND TIME OF LATEST TRANSACTION |
|---|
| control field |
20200413152911.0 |
| 006 - FIXED-LENGTH DATA ELEMENTS--ADDITIONAL MATERIAL CHARACTERISTICS |
|---|
| fixed length control field |
m eo d |
| 007 - PHYSICAL DESCRIPTION FIXED FIELD--GENERAL INFORMATION |
|---|
| fixed length control field |
cr cn |||m|||a |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION |
|---|
| fixed length control field |
130814s2013 caua foab 000 0 eng d |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| International Standard Book Number |
9781627050197 (electronic bk.) |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER |
|---|
| Canceled/invalid ISBN |
9781627050180 (pbk.) |
| 024 7# - OTHER STANDARD IDENTIFIER |
|---|
| Standard number or code |
10.2200/S00520ED1V01Y201307DCT011 |
| Source of number or code |
doi |
| 035 ## - SYSTEM CONTROL NUMBER |
|---|
| System control number |
(CaBNVSL)swl00402645 |
| 035 ## - SYSTEM CONTROL NUMBER |
|---|
| System control number |
(OCoLC)855857834 |
| 040 ## - CATALOGING SOURCE |
|---|
| Original cataloging agency |
CaBNVSL |
| Transcribing agency |
CaBNVSL |
| Modifying agency |
CaBNVSL |
| 050 #4 - LIBRARY OF CONGRESS CALL NUMBER |
|---|
| Classification number |
QA166.247 |
| Item number |
.B273 2013 |
| 082 04 - DEWEY DECIMAL CLASSIFICATION NUMBER |
|---|
| Classification number |
511.56 |
| Edition number |
23 |
| 090 ## - LOCALLY ASSIGNED LC-TYPE CALL NUMBER (OCLC); LOCAL CALL NUMBER (RLIN) |
|---|
| Classification number (OCLC) (R) ; Classification number, CALL (RLIN) (NR) |
|
| Local cutter number (OCLC) ; Book number/undivided call number, CALL (RLIN) |
MoCl |
| 100 1# - MAIN ENTRY--PERSONAL NAME |
|---|
| Personal name |
Barenboim, Leonid. |
| 245 10 - TITLE STATEMENT |
|---|
| Title |
Distributed graph coloring |
| Medium |
[electronic resource] : |
| Remainder of title |
fundamentals and recent developments / |
| Statement of responsibility, etc. |
Leonid Barenboim and Michael Elkin. |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. |
|---|
| Place of publication, distribution, etc. |
San Rafael, Calif. (1537 Fourth Street, San Rafael, CA 94901 USA) : |
| Name of publisher, distributor, etc. |
Morgan & Claypool, |
| Date of publication, distribution, etc. |
c2013. |
| 300 ## - PHYSICAL DESCRIPTION |
|---|
| Extent |
1 electronic text (xiii, 157 p.) : |
| Other physical details |
ill., digital file. |
| 490 1# - SERIES STATEMENT |
|---|
| Series statement |
Synthesis lectures on distributed computing theory, |
| International Standard Serial Number |
2155-1634 ; |
| Volume/sequential designation |
# 11 |
| 538 ## - SYSTEM DETAILS NOTE |
|---|
| System details note |
Mode of access: World Wide Web. |
| 538 ## - SYSTEM DETAILS NOTE |
|---|
| System details note |
System requirements: Adobe Acrobat Reader. |
| 500 ## - GENERAL NOTE |
|---|
| General note |
Part of: Synthesis digital library of engineering and computer science. |
| 500 ## - GENERAL NOTE |
|---|
| General note |
Series from website. |
| 504 ## - BIBLIOGRAPHY, ETC. NOTE |
|---|
| Bibliography, etc. note |
Includes bibliographical references (p. 149-155). |
| 505 0# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
1. Introduction -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
2. Basics of graph theory -- 2.1 Graphs with large girth and large chromatic number -- 2.2 Planar graphs -- 2.3 Arboricity -- 2.3.1 Nash-Williams theorem -- 2.3.2 Degeneracy and arboricity -- 2.4 Defective coloring -- 2.5 Edge-coloring and matchings -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
3. Basic distributed graph coloring algorithms -- 3.1 The distributed message-passing LOCAL model -- 3.2 Basic color reduction -- 3.3 Orientations -- 3.4 The algorithm of Cole and Vishkin -- 3.5 Extensions to graphs with bounded maximum degree -- 3.6 An improved coloring algorithm for graphs with bounded maximum degree -- 3.7 A faster ([delta plus] 1)-coloring -- 3.8 Kuhn-Wattenhofer color reduction technique and its applications -- 3.9 A reduction from ([delta plus] 1)-coloring to MIS -- 3.10 Linial's algorithm -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
4. Lower bounds -- 4.1 Coloring unoriented trees -- 4.1.1 The first proof -- 4.1.2 The second proof -- 4.2 Coloring the n-path Pn -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
5. Forest-decomposition algorithms and applications -- 5.1 H-partition -- 5.2 An O(a)-coloring -- 5.3 Faster coloring -- 5.4 MIS algorithms -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
6. Defective coloring -- 6.1 Employing defective coloring for computing legal coloring -- 6.2 Defective coloring algorithms -- 6.2.1 Procedure refine -- 6.2.2 Procedure defective-color -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
7. Arbdefective coloring -- 7.1 Small arboricity decomposition -- 7.2 Efficient coloring algorithms -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
8. Edge-coloring and maximal matching -- 8.1 Edge-coloring and maximal matching using forest-decomposition -- 8.2 Edge-coloring using bounded neighborhood independence -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
9. Network decompositions -- 9.1 Applications of network decompositions -- 9.2 Ruling sets and forests -- 9.3 Constructing network decompositions -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
10. Introduction to distributed randomized algorithms -- 10.1 Simple algorithms -- 10.2 A faster O([delta])-coloring algorithm -- 10.3 Randomized MIS -- 10.3.1 A high-level description -- 10.3.2 Procedure decide -- 10.4 Randomized maximal matching -- 10.5 Graphs with bounded arboricity -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
11. Conclusion and open questions -- 11.1 Problems that can be solved in polylogarithmic time -- 11.2 Problems that can be solved in (sub)linear in [delta] time -- 11.3 Algorithms for restricted graph families -- 11.4 Randomized algorithms -- |
| 505 8# - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
Bibliography -- Authors' biographies. |
| 506 1# - RESTRICTIONS ON ACCESS NOTE |
|---|
| Terms governing access |
Abstract freely available; full-text restricted to subscribers or individual document purchasers. |
| 510 0# - CITATION/REFERENCES NOTE |
|---|
| Name of source |
Compendex |
| 510 0# - CITATION/REFERENCES NOTE |
|---|
| Name of source |
INSPEC |
| 510 0# - CITATION/REFERENCES NOTE |
|---|
| Name of source |
Google scholar |
| 510 0# - CITATION/REFERENCES NOTE |
|---|
| Name of source |
Google book search |
| 520 3# - SUMMARY, ETC. |
|---|
| Summary, etc. |
The focus of this monograph is on symmetry breaking problems in the message-passing model of distributed computing. In this model a communication network is represented by a n -vertex graph G = (V,E), whose vertices host autonomous processors. The processors communicate over the edges of G in discrete rounds. The goal is to devise algorithms that use as few rounds as possible. |
| 530 ## - ADDITIONAL PHYSICAL FORM AVAILABLE NOTE |
|---|
| Additional physical form available note |
Also available in print. |
| 588 ## - SOURCE OF DESCRIPTION NOTE |
|---|
| Source of description note |
Title from PDF t.p. (viewed on August 14, 2013). |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name entry element |
Graph coloring |
| General subdivision |
Mathematical models. |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name entry element |
Broken symmetry (Physics) |
| 650 #0 - SUBJECT ADDED ENTRY--TOPICAL TERM |
|---|
| Topical term or geographic name entry element |
Electronic data processing |
| General subdivision |
Distributed processing. |
| 653 ## - INDEX TERM--UNCONTROLLED |
|---|
| Uncontrolled term |
distributed symmetry breaking |
| 653 ## - INDEX TERM--UNCONTROLLED |
|---|
| Uncontrolled term |
maximal independent set |
| 653 ## - INDEX TERM--UNCONTROLLED |
|---|
| Uncontrolled term |
maximal matching |
| 653 ## - INDEX TERM--UNCONTROLLED |
|---|
| Uncontrolled term |
coloring |
| 653 ## - INDEX TERM--UNCONTROLLED |
|---|
| Uncontrolled term |
deterministic algorithms |
| 653 ## - INDEX TERM--UNCONTROLLED |
|---|
| Uncontrolled term |
randomized algorithms |
| 653 ## - INDEX TERM--UNCONTROLLED |
|---|
| Uncontrolled term |
arboricity |
| 700 1# - ADDED ENTRY--PERSONAL NAME |
|---|
| Personal name |
Elkin, Michael. |
| 776 08 - ADDITIONAL PHYSICAL FORM ENTRY |
|---|
| Relationship information |
Print version: |
| International Standard Book Number |
9781627050180 |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE |
|---|
| Uniform title |
Synthesis digital library of engineering and computer science. |
| 830 #0 - SERIES ADDED ENTRY--UNIFORM TITLE |
|---|
| Uniform title |
Synthesis lectures on distributed computing theory ; |
| Volume/sequential designation |
# 11. |
| International Standard Serial Number |
2155-1634 |
| 856 42 - ELECTRONIC LOCATION AND ACCESS |
|---|
| Materials specified |
Abstract with links to resource |
| Uniform Resource Identifier |
http://ieeexplore.ieee.org/servlet/opac?bknumber=6813010 |
| 856 40 - ELECTRONIC LOCATION AND ACCESS |
|---|
| Materials specified |
Abstract with links to full text |
| Uniform Resource Identifier |
http://dx.doi.org/10.2200/S00520ED1V01Y201307DCT011 |
