000 03680nam a22005415i 4500
001 978-3-642-27875-4
003 DE-He213
005 20140220083309.0
007 cr nn 008mamaa
008 120423s2012 gw | s |||| 0|eng d
020 _a9783642278754
_9978-3-642-27875-4
024 7 _a10.1007/978-3-642-27875-4
_2doi
050 4 _aQA164-167.2
072 7 _aPBV
_2bicssc
072 7 _aMAT036000
_2bisacsh
082 0 4 _a511.6
_223
100 1 _aNešetřil, Jaroslav.
_eauthor.
245 1 0 _aSparsity
_h[electronic resource] :
_bGraphs, Structures, and Algorithms /
_cby Jaroslav Nešetřil, Patrice Ossona de Mendez.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg,
_c2012.
300 _aXXIII, 457p. 132 illus., 100 illus. in color.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aAlgorithms and Combinatorics,
_x0937-5511 ;
_v28
505 0 _aPart 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 .
520 _aThis 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 Nešetřil 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.
650 0 _aMathematics.
650 0 _aComputer software.
650 0 _aComputational complexity.
650 0 _aCombinatorics.
650 0 _aDiscrete groups.
650 0 _aLogic, Symbolic and mathematical.
650 1 4 _aMathematics.
650 2 4 _aCombinatorics.
650 2 4 _aDiscrete Mathematics in Computer Science.
650 2 4 _aConvex and Discrete Geometry.
650 2 4 _aMathematical Logic and Foundations.
650 2 4 _aAlgorithm Analysis and Problem Complexity.
700 1 _aOssona de Mendez, Patrice.
_eauthor.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer eBooks
776 0 8 _iPrinted edition:
_z9783642278747
830 0 _aAlgorithms and Combinatorics,
_x0937-5511 ;
_v28
856 4 0 _uhttp://dx.doi.org/10.1007/978-3-642-27875-4
912 _aZDB-2-SMA
999 _c102669
_d102669