Skip to main content
Cover for Sparsity


Graphs, Structures, and Algorithms (Algorithms and Combinatorics #28)

Jaroslav Nesetřil, Patrice Ossona De Mendez


List Price: 99.99*
* Individual store prices may vary.

Other Editions of This Title:
Paperback (5/9/2014)


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​.

Springer, 9783642278747, 459pp.

Publication Date: April 25, 2012