Sparsity : graphs, structures, and algorithms
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...
محفوظ في:
| المؤلفون الرئيسيون: | , , |
|---|---|
| التنسيق: | Livre numérique |
| اللغة: | Anglais |
| منشور في: |
Berlin, Heidelberg :
Springer Berlin Heidelberg
[20..].
Cham : Springer Nature |
| الطبعة: | 1st ed. 2012. |
| سلاسل: | Algorithms and Combinatorics
28 |
| الموضوعات: | |
| الوصول للمادة أونلاين: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| ملاحظة: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Sparsity, graphs, structures, and algorithms, Jaroslav Nešetřil, Patrice Ossona de Mendez, Berlin, Springer, 2012, 1 volume (xxiii-457 pages), Algorithms and Combinatorics, 978-3-642-27874-7 • Sparsity, graphs, structures, and algorithms, Jaroslav Nešetřil, Patrice Ossona de Mendez, Berlin, Springer, 2012, 1 volume (xxiii-457 pages), Algorithms and Combinatorics, 978-3-642-27874-7 • Sparsity, Texte imprimé, 9783642278761 • Sparsity, Texte imprimé, 9783642427763 |
جدول المحتويات:
- 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
- Part I Presentation
- Part II. The Theory
- Part III Applications
- 1. Introduction
- 2. A Few Problems
- 3. Commented Contents
- 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
- 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