Linear time low tree-width partitions and algorithmic consequences

DOI10.1145/1132516.1132575MaRDI QIDQ2931403zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. 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

bounded expansioncolorationfirst-order logicfraternal augmentationgraph minorsubgraph isomorphismtree-width

Mathematics Subject Classification ID

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

Recommendations

• Grad and classes with bounded expansion. II: Algorithmic aspects
• Testing first-order properties for subclasses of sparse graphs
• Grad and classes with bounded expansion. I: Decompositions
• Partitioning graphs of bounded tree-width
• Fraternal Augmentations of graphs, Coloration and Minors

Cited in

(42)

• 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
• Treedepth bounds in linear colorings
• Parameterized extension complexity of independent set and related problems
• 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
• On nowhere dense graphs
• Distance-two coloring of sparse graphs
• Bounds on half graph orders in powers of sparse graphs
• Obstructions for tree-depth
• Finding small separators in linear time via treewidth reduction
• Many Facets of Dualities
• On recognizing graphs by numbers of homomorphisms
• Deciding first-order properties of locally tree-decomposable structures
• Kernelization using structural parameters on sparse graph classes
• Fraternal Augmentations of graphs, Coloration and Minors
• NP for Combinatorialists
• Efficient First-Order Model-Checking Using Short Labels
• Forbidden graphs for tree-depth
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Colouring, constraint satisfaction, and complexity
• Colouring edges with many colours in cycles
• Recovering sparse graphs
• Algorithmic properties of sparse digraphs
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Shortest-path queries in static networks
• Testing first-order properties for subclasses of sparse graphs
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• A distributed low tree-depth decomposition algorithm for bounded expansion classes
• Compact labelings for efficient first-order model-checking
• How many F's are there in G?
• Characterisations and examples of graph classes with bounded expansion
• Decomposition horizons and a characterization of stable hereditary classes of graphs
• On first-order transductions of classes of graphs
• LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
• Computing vertex-surjective homomorphisms to partially reflexive trees
• First-order transductions of graphs (invited talk)
• On low tree-depth decompositions
• Small graph classes and bounded expansion

This page was built for publication: Linear time low tree-width partitions and algorithmic consequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931403)