Contraction decomposition in h-minor-free graphs and algorithmic applications

DOI10.1145/1993636.1993696zbMath1288.05256OpenAlexW1988652875MaRDI QIDQ5419114

Erik D. Demaine, Ken-ichi Kawarabayashi, Mohammad Taghi Hajiaghayi

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

decompositiongraph minorgraph contraction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (17)

A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface ⋮ Max-Cut Under Graph Constraints ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Unnamed Item ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Approximating graph-constrained max-cut ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Unnamed Item

This page was built for publication: Contraction decomposition in h-minor-free graphs and algorithmic applications