Contraction decomposition in h-minor-free graphs and algorithmic applications
From MaRDI portal
Publication:5419114
DOI10.1145/1993636.1993696zbMath1288.05256MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C10: Planar graphs; geometric and topological aspects of graph theory
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Unnamed Item, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Unnamed Item, Spanning closed walks and TSP in 3-connected planar graphs, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, An exact combinatorial algorithm for minimum graph bisection, Sublinear separators, fragility and subexponential expansion, Approximating graph-constrained max-cut, Polynomial bounds for centered colorings on proper minor-closed graph classes, Approximation algorithms for connected maximum cut and related problems, Structural sparsity of complex networks: bounded expansion in random models and real-world graphs, Linear kernels for outbranching problems in sparse digraphs, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, An LP-based approximation algorithm for the generalized traveling salesman path problem, Max-Cut Under Graph Constraints, A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface
