Approximation algorithms via contraction decomposition
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 6381654
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
- Contractions of Planar Graphs in Polynomial Time
Cites work
- scientific article; zbMATH DE number 1670877 (Why is no real title available?)
- scientific article; zbMATH DE number 1303538 (Why is no real title available?)
- scientific article; zbMATH DE number 1306896 (Why is no real title available?)
- scientific article; zbMATH DE number 2119747 (Why is no real title available?)
- scientific article; zbMATH DE number 6297711 (Why is no real title available?)
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- A separator theorem for graphs of bounded genus
- A subset spanner for Planar graphs, with application to subset TSP
- Algorithms – ESA 2005
- Algorithms – ESA 2005
- All structured programs have small tree width and good register allocation
- Applications of a Planar Separator Theorem
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs
- Automata, Languages and Programming
- Bidimensional Parameters and Local Treewidth
- Combinatorial Local Planarity and the Width of Graph Embeddings
- Diameter and treewidth in minor-closed graph families
- Diameter and treewidth in minor-closed graph families, revisited
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Expander flows, geometric embeddings and graph partitioning
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Graph minors and graphs on surfaces
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. XI: Circuits on a surface
- Graph minors. XVI: Excluding a non-planar graph
- Graphs on surfaces
- Local tree-width, excluded minors, and approximation algorithms
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Multiple-source shortest paths in planar graphs
- SOFSEM 2005: Theory and Practice of Computer Science
- Separating and nonseparating disjoint homotopic cycles in graph embeddings
- Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
- The Bidimensional Theory of Bounded-Genus Graphs
- Zero knowledge and the chromatic number
- Über eine Eigenschaft der ebenen Komplexe
Cited in
(10)- An LP-based approximation algorithm for the generalized traveling salesman path problem
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- scientific article; zbMATH DE number 6381654 (Why is no real title available?)
- Exact and approximation algorithms for computing optimal fat decompositions
- Bounding tree-width via contraction on the projective plane and torus
- Some recent progress and applications in graph minor theory
- A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
- Contraction decomposition in \(h\)-minor-free graphs and algorithmic applications
- The greedy spanner is existentially optimal
- A decomposition based algorithm for maximal contractions
This page was built for publication: Approximation algorithms via contraction decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1945289)
