Atnaujinkite slapukų nuostatas

Sparsity: Graphs, Structures, and Algorithms 2012 ed. [Kietas viršelis]

,
  • Formatas: Hardback, 459 pages, aukštis x plotis: 235x155 mm, weight: 887 g, 100 Illustrations, color; 32 Illustrations, black and white; XXIII, 459 p. 132 illus., 100 illus. in color., 1 Hardback
  • Serija: Algorithms and Combinatorics 28
  • Išleidimo metai: 25-Apr-2012
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • ISBN-10: 3642278744
  • ISBN-13: 9783642278747
Kitos knygos pagal šią temą:
Sparsity: Graphs, Structures, and Algorithms 2012 ed.Didesnis paveikslėlis
  • Formatas: Hardback, 459 pages, aukštis x plotis: 235x155 mm, weight: 887 g, 100 Illustrations, color; 32 Illustrations, black and white; XXIII, 459 p. 132 illus., 100 illus. in color., 1 Hardback
  • Serija: Algorithms and Combinatorics 28
  • Išleidimo metai: 25-Apr-2012
  • Leidėjas: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • ISBN-10: 3642278744
  • ISBN-13: 9783642278747
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9783642278747.html
Raktažodžiai:
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 Neetil 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.

Recenzijos

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)

This is an excellent and useful book for all researchers in mathematics, computer science, logic, and even in any field in physical science, who seek the tools available for analysis of the properties of discrete structures, and particularly, sparse structures. (Tadashi Sakuma, zbMATH, Vol. 1268, 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, Computing Reviews, October, 2012)

Presentation
1 Introduction
3(4)
2 A Few Problems
7(14)
2.1 Breaking a Mesh
7(2)
2.2 Forging Alliances
9(3)
2.3 Are Symmetries Frequent?
12(2)
2.4 Large Matchings on a Torus
14(1)
2.5 Homomorphism Dualities
15(6)
The Theory
3 Prolegomena
21(40)
3.1 Graphs
21(1)
3.2 Average Degree and Minimum Degree
22(1)
3.3 Graph Degeneracy and Orientations
23(4)
3.4 Girth
27(3)
3.5 Minors
30(3)
3.6 Width, Separators and Expanders
33(6)
3.7 Homomorphisms
39(7)
3.8 Relational Structures and First-Order Logic
46(6)
3.9 Ramsey Theory
52(2)
3.10 Graph Parameters
54(2)
3.11 Computational complexity
56(5)
Exercises
59(2)
4 Measuring Sparsity
61(28)
4.1 Basic Definitions
61(1)
4.2 Shallow Minors
62(3)
4.3 Shallow Topological Minors
65(1)
4.4 Grads and Top-Grads
66(2)
4.5 Polynomial Equivalence of Grads and Top-Grads
68(9)
4.6 Relation with Chromatic Number
77(3)
4.7 Stability of Grads by Lexicographic Product
80(3)
4.8 Shallow Immersions
83(3)
4.9 Generalized Coloring Numbers
86(3)
Exercises
88(1)
5 Classes and Their Classification
89(26)
5.1 Operations on Classes and Resolutions
91(6)
5.2 Logarithmic Density and Concentration
97(3)
5.3 Classification of Classes by Clique Minors
100(2)
5.4 Classification by Density---Trichotomy of Classes
102(2)
5.5 Classes with Bounded Expansion
104(3)
5.6 Classes with Locally Bounded Expansion
107(1)
5.7 A Historical Note on Connection to Model Theory
108(2)
5.8 Classes of Relational Structures
110(5)
Exercises
113(2)
6 Bounded Height Trees and Tree-Depth
115(30)
6.1 Definitions and Basic Properties
115(2)
6.2 Tree-Depth, Minors and Paths
117(5)
6.3 Compact Elimination Trees and Weak-Coloring
122(1)
6.4 Tree-Depth, Tree-Width and Vertex Separators
123(2)
6.5 Centered Colorings
125(3)
6.6 Cycle Rank
128(2)
6.7 Games and a Min-Max Formula for Tree-Depth
130(2)
6.8 Reductions and Finiteness
132(4)
6.9 Ehrenfeucht-Fraisse Games
136(1)
6.10 Well Quasi-orders
136(4)
6.11 The Homomorphism Quasi-order
140(5)
Exercises
142(3)
7 Decomposition
145(30)
7.1 Motivation, Low Tree-Width and Low Tree-Depth
145(8)
7.2 Low Tree-Depth Coloring and p-Centered Colorings
153(1)
7.3 Transitive Fraternal Augmentation
154(4)
7.4 Fraternal Augmentations of Graphs
158(10)
7.5 The Weak-Coloring Approach
168(7)
Exercises
173(2)
8 Independence
175(20)
8.1 How Wide is a Class?
175(4)
8.2 Wide Classes
179(1)
8.3 Finding d-Independent Sets in Graphs
180(5)
8.4 Quasi-Wide Classes
185(3)
8.5 Almost Wide Classes
188(1)
8.6 A Nice (Asymmetric) Application
189(6)
Exercises
194(1)
9 First-Order CSP, Limits and Homomorphism Dualities
195(32)
9.1 Introduction
195(2)
9.2 Homomorphism Dualities and the Functor U
197(6)
9.3 Metrics on the Homomorphism Order
203(9)
9.4 Left Limits and Countable Structures
212(5)
9.5 Right Limits and Full Limits
217(10)
Exercises
224(3)
10 Preservation Theorems
227(26)
10.1 Introduction
227(1)
10.2 Primitive Positive Theories and Left Limits
228(5)
10.3 Theories and Countable Structures
233(2)
10.4 Primitive Positive Theories Again
235(2)
10.5 Quotient Metric Spaces
237(3)
10.6 The Topological Preservation Theorem
240(2)
10.7 Homomorphism Preservation Theorems
242(4)
10.8 Homomorphism Preservation Theorems for Finite Structures
246(7)
Exercises
251(2)
11 Restricted Homomorphism Dualities
253(24)
11.1 Introduction
253(1)
11.2 Classes with All Restricted Dualities
254(1)
11.3 Characterization of Classes with All Restricted Dualities by Distances
254(2)
11.4 Characterization of Classes with All Restricted Dualities by Local Homomorphisms
256(4)
11.5 Restricted Dualities in Bounded Expansion Classes
260(2)
11.6 Characterization of Classes with All Restricted Dualities by Reorientations
262(2)
11.7 Characterization of Classes with All Restricted Dualities by Subdivisions
264(1)
11.8 First-Order Definable H-Colorings
265(4)
11.9 Consequences and Related Problems
269(8)
Exercises
274(3)
12 Counting
277(22)
12.1 Introduction
277(4)
12.2 Generalized Sunflowers
281(2)
12.3 Counting Patterns of Bounded Height in a Colored Forest
283(6)
12.4 Counting in Graphs with Bounded Tree Depth
289(3)
12.5 Counting Subgraphs in Graphs
292(1)
12.6 Counting Subgraphs in Graphs in a Class
293(6)
Exercises
296(3)
13 Back to Classes
299(14)
13.1 Resolutions
299(3)
13.2 Parameters
302(2)
13.3 Nowhere Dense Classes
304(1)
13.4 Bounded Expansion Classes
305(1)
13.5 Bounded Tree-Depth Classes
306(2)
13.6 Remarks on Structures
308(5)
Applications
14 Classes with Bounded Expansion - Examples
313(26)
14.1 Random Graphs (Erdos-Renyi Model)
314(5)
14.2 Crossing Number
319(2)
14.3 Queue and Stack Layouts
321(1)
14.4 Queue Number
322(5)
14.5 Stack Number
327(1)
14.6 Non-repetitive Colorings
328(11)
Exercises
337(2)
15 Some Applications
339(24)
15.1 Finding Matching and Paths
339(11)
15.2 Burr-Erdos Conjecture
350(2)
15.3 The Game Chromatic Number
352(3)
15.4 Fiedler Value of Classes with Sublinear Separators
355(8)
16 Property Testing, Hyperfiniteness and Separators
363(18)
16.1 Property Testing
363(5)
16.2 Weakly Hyperfinite Classes
368(1)
16.3 Vertex Separators
369(4)
16.4 Sub-exponential ω-Expansion
373(8)
Exercises
379(2)
17 Core Algorithms
381(16)
17.1 Data Structures and Algorithmic Aspects
381(5)
17.2 p-Tree-Depth Coloring
386(4)
17.3 Computing and Approximating Tree-Depth
390(2)
17.4 Counting Homomorphisms to Graphs with Bounded Tree-Depth
392(1)
17.5 First-Order Cores of Graphs with Bounded Tree-Depth
393(4)
Exercises
396(1)
18 Algorithmic Applications
397(14)
18.1 Introduction
397(2)
18.2 Truncated Distances
399(1)
18.3 The Subgraph Isomorphism Problem and Boolean Queries
400(2)
18.4 The Distance-d Dominating Set Problem
402(2)
18.5 General First-Order Model Checking
404(3)
18.6 Counting Versions of Model Checking
407(4)
Exercises
410(1)
19 Further Directions
411(6)
20 Solutions and Hints for some of the Exercises
417(14)
References 431(20)
Index 451