Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
From MaRDI portal
Publication:1880778
DOI10.1016/j.jcss.2003.12.001zbMath1073.68063OpenAlexW2029854525MaRDI QIDQ1880778
Prabhakar Ragde, Naomi Nishimura, Dimitrios M. Thilikos, Mohammad Taghi Hajiaghayi, Erik D. Demaine
Publication date: 1 October 2004
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2003.12.001
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Approximation algorithms for treewidth, Approximation algorithms via contraction decomposition, \textsc{max-cut} and containment relations in graphs, Subexponential parameterized algorithms, Counting the number of perfect matchings in \(K_{5}\)-free graphs, Linearity of grid minors in treewidth with applications through bidimensionality, Structure of polynomial-time approximation, max-cut and Containment Relations in Graphs, Optimization and Recognition for K 5-minor Free Graphs in Linear Time, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Unnamed Item
Cites Work
- Graph minors. III. Planar tree-width
- Improved algorithms for graph four-connectivity
- An approach to the subgraph homeomorphism problem
- Simplicial decompositions of graphs: A survey of applications
- Graph minors. X: Obstructions to tree-decomposition
- Decomposing infinite graphs
- A new graph triconnectivity algorithm and its parallelization
- On the complexity of finding iso- and other morphisms for partial \(k\)- trees
- A partial k-arboretum of graphs with bounded treewidth
- Call routing and the ratcatcher
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Treewidth for graphs with small chordality
- On interval routing schemes and treewidth
- Diameter and treewidth in minor-closed graph families
- On simple characterizations of k-trees
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The extremal function for complete minors
- Parallel approximation schemes for problems on planar graphs
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Vertex Cover: Further Observations and Further Improvements
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Deciding first-order properties of locally tree-decomposable structures
- Characterization and Recognition of Partial 3-Trees
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Depth-First Search and Kuratowski Subgraphs
- Applications of a Planar Separator Theorem
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
- Partitioning Planar Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Treewidth of Circular-Arc Graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Subgraph Isomorphism in Planar Graphs and Related Problems
- The Pathwidth and Treewidth of Cographs
- Dividing a Graph into Triconnected Components
- Treewidth and Pathwidth of Permutation Graphs
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- On Linear Recognition of Tree-Width at Most Four
- TREEWIDTH OF CIRCLE GRAPHS
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Node-and edge-deletion NP-complete problems
- Depth-First Search and Linear Graph Algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
