Sparsity
Graphs, Structures, and Algorithms
Published in May 2012
Book
Hardback
XXIII, 457 pages
978-3-642-27874-7 (ISBN)
Description
This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants.
This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms.
Jaroslav NeSetril is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris.
This book is related to the material presented by the first author at ICM 2010.
Reviews / Votes
From the reviews: "This well-crafted and well-written work ... brings the authors' vast knowledge, expertise, taste, and judgment to bear on an increasingly important and mainstream subject. ... This is a much-needed book devoted to the systematic study of sparse graphs and sparse classes of structures. ... This is an important and useful book. It contains a wealth of up-to-date material, some of which is not readily available in research papers. ... A researcher in graph theory or related fields will find this an excellent reference work." (József Balogh, Mathematical Reviews, March, 2013) "The book is very well written and diagrammed to beautifully present the theory supporting the study of sparse and dense objects. ... the book contains up-to-date research topics laid out in an amazing chain of thoughts. Almost every chapter ends with exercises, aiding professors in advanced graduate courses. The extensive list of references, together with conjectures and open problems, offers professors, students, and researchers ... profound knowledge on the sparsity of graphs, all in one great book." (Andre Maximo, ACM Computing Reviews, October, 2012)More details
Product info
Book
Series
Edition
2012
Language
English
Place of publication
Heidelberg
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Graduate
Illustrations
32 s/w Abbildungen, 100 farbige Abbildungen
105 farbige Abbildungen
Dimensions
Height: 241 mm
Width: 160 mm
Thickness: 32 mm
Weight
887 gr
ISBN-13
978-3-642-27874-7 (9783642278747)
DOI
10.1007/978-3-642-27875-4
Schweitzer Classification
Other editions
Additional editions
Book
05/2014
Springer
€96.29
Shipment within 7-9 days
E-Book
04/2012
1st Edition
Springer
€96.29
Available for download
Content
Part I Presentation: 1. Introduction.- 2. A Few Problems.- 3. Commented Contents.- Part II. The Theory: 4. Prolegomena.- 5. Measuring Sparsity.- 6. Classes and their Classification.- 7. Bounded Height Trees and Tree-Depth.- 8. Decomposition.- 9. Independence.- 10. First-Order Constraint Satisfaction Problems and Homomorphism Dualities.- 11. Restricted Homomorphism Dualities.- 12. Counting.- 13. Back to Classes.- Part III Applications: 14. Classes with Bounded Expansion - Examples.- 15. Property Testing, Hyperfiniteness and Separators.- 16. Algorithmic Applications.- 17. Other Applications.- 18. Conclusion.- Bibliography.- Index.- List of Symbols¿.