You are here

Sparsity: Graphs, Structures, and Algorithms

Jaroslav Nešetřil and Patrice Ossona de Mendez
Publisher: 
Springer
Publication Date: 
2012
Number of Pages: 
457
Format: 
Hardcover
Series: 
Algorithms and Combinatorics 28
Price: 
79.95
ISBN: 
9783642278747
Category: 
Monograph
We do not plan to review this book.

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