Approximation algorithms via contraction decomposition

DOI10.1007/s00493-010-2341-5zbMath1274.05445OpenAlexW3136485547MaRDI QIDQ1945289

Bojan Mohar, Erik D. Demaine, Mohammad Taghi Hajiaghayi

Publication date: 5 April 2013

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/63808

zbMATH Keywords

graphs of bounded treewidthcontracting edgesgraphs of bounded (Euler) genusobtaining PTASs for contraction-closed problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Related Items

A Fixed Parameter Tractable Approximation Scheme for the Optimal Cut Graph of a Surface, Some recent progress and applications in graph minor theory, Bounding tree-width via contraction on the projective plane and torus, An LP-based approximation algorithm for the generalized traveling salesman path problem, Polynomial bounds for centered colorings on proper minor-closed graph classes, The Greedy Spanner Is Existentially Optimal, Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• All structured programs have small tree width and good register allocation
• Zero knowledge and the chromatic number
• Graph minors. XI: Circuits on a surface
• Graph minors. XVI: Excluding a non-planar graph
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• Local tree-width, excluded minors, and approximation algorithms
• Über eine Eigenschaft der ebenen Komplexe
• A subset spanner for Planar graphs, with application to subset TSP
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• A separator theorem for graphs of bounded genus
• The Bidimensional Theory of Bounded-Genus Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Applications of a Planar Separator Theorem
• Combinatorial Local Planarity and the Width of Graph Embeddings
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Approximation algorithms for NP-complete problems on planar graphs
• Bidimensional Parameters and Local Treewidth
• Automata, Languages and Programming
• Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
• Algorithms – ESA 2005
• Algorithms – ESA 2005
• SOFSEM 2005: Theory and Practice of Computer Science
• Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
• Expander flows, geometric embeddings and graph partitioning