How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
From MaRDI portal
Publication:3508575
DOI10.1007/978-3-540-74839-7_27zbMath1141.68524OpenAlexW1553367638MaRDI QIDQ3508575
Publication date: 1 July 2008
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_27
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 algorithms (graph-theoretic aspects) (05C85)
Related Items
How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Dynamic programming and planarity: improved tree-decomposition based algorithms, Computational study on planar dominating set problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimal triangulations of graphs: a survey
- Finding small simple cycle separators for 2-connected planar graphs
- Graph minors. X: Obstructions to tree-decomposition
- Counting clique trees and computing perfect elimination schemes in parallel
- Characterizations and algorithmic applications of chordal graph embeddings
- Chordal embeddings of planar graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Tour Merging via Branch-Decomposition
- The Use of Linear Graphs in Gauss Elimination
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm
- A Separator Theorem for Planar Graphs
- Power of Natural Semijoins
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Subgraph Isomorphism in Planar Graphs and Related Problems
- The Pathwidth and Treewidth of Cographs
- Dynamic Programming and Fast Matrix Multiplication
- Algorithms – ESA 2005
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
