Linear time low tree-width partitions and algorithmic consequences

DOI10.1145/1132516.1132575zbMath1301.05268OpenAlexW2068312052MaRDI QIDQ2931403

Jaroslav Nešetřil, Patrice Ossona de Mendez

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132575

zbMATH Keywords

first-order logicgraph minorsubgraph isomorphismtree-widthbounded expansioncolorationfraternal augmentation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Kernelization using structural parameters on sparse graph classes, Parameterized extension complexity of independent set and related problems, NP for Combinatorialists, Forbidden graphs for tree-depth, On low tree-depth decompositions, A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth, Efficient First-Order Model-Checking Using Short Labels, Compact labelings for efficient first-order model-checking, Grad and classes with bounded expansion. I: Decompositions, Grad and classes with bounded expansion. II: Algorithmic aspects, Forbidden lifts (NP and CSP for combinatorialists), Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities, Unnamed Item, On nowhere dense graphs, Many Facets of Dualities, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Bounds on half graph orders in powers of sparse graphs, Distance-two coloring of sparse graphs, How many \(F\)'s are there in \(G\)?, Colouring, constraint satisfaction, and complexity, Colouring edges with many colours in cycles, Characterisations and examples of graph classes with bounded expansion, Small graph classes and bounded expansion, On the $AC^0$ Complexity of Subgraph Isomorphism, Shortest-path queries in static networks, LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth, Computing vertex-surjective homomorphisms to partially reflexive trees, Unnamed Item, On recognizing graphs by numbers of homomorphisms, A distributed low tree-depth decomposition algorithm for bounded expansion classes, Fraternal augmentations, arrangeability and linear Ramsey numbers, A surprising permanence of old motivations (a not-so-rigid story), Colouring graphs with bounded generalized colouring number, Obstructions for Tree-depth, Fraternal Augmentations of graphs, Coloration and Minors