- A Single-Exponential Time 2-Approximation Algorithm for Treewidth
2022/02/01 by Tuukka Korhonen · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Treewidth #Tree decomposition #Combinatorics #Vertex (graph theory) #Exponential function #Mathematics #Tree-depth #Graph #Integer (computer science) #Algorithm #Discrete mathematics #1-planar graph #Pathwidth #Computer science #Chordal graph #Line graph #Mathematical analysis
- Planar Graphs Have Bounded Queue-Number
2019/04/30 by Vida Dujmović, Gwenaël Joret, Piotr Micek +3 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Bounded function #Clique-sum #Computational Geometry and Mesh Generation #Graph product #Indifference graph #Limits and Structures in Graph Theory #Pathwidth #Planar graph #Tree-depth #Treewidth
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
2018/06/16 by Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh +2 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods #Treewidth #Combinatorics #Mathematics #Time complexity #Tree decomposition #Parameterized complexity #Tree-depth #Discrete mathematics #Graph #Algorithm #Pathwidth #Chordal graph #1-planar graph #Line graph
- Polynomial Bounds for the Grid-Minor Theorem
2016/12/17 by Chandra Chekuri, Julia Chuzhoy · 7 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph minor #Interconnection Networks and Systems #Line graph #Mathematics #Minor (academic) #Partial k-tree #Pathwidth #Planar graph #Polynomial #Robertson–Seymour theorem #Tree decomposition #Tree-depth #Treewidth #Upper and lower bounds #Voltage graph
- A ck n 5-Approximation Algorithm for Treewidth
2016/01/01 by Hans L. Bodlaender, Pål Grønås Drange, Markus Sortland Dregi +3 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #Treewidth #Tree decomposition #Mathematics #Combinatorics #Exponential function #Tree-depth #Vertex (graph theory) #Algorithm #Subroutine #Discrete mathematics #Approximation algorithm #Partial k-tree #Graph #1-planar graph #Pathwidth #Computer science #Chordal graph #Line graph
- Approximation Algorithms for Treewidth
2008/04/01 by Eyal Amir · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Approximation algorithm #Chordal graph #Clique-sum #Clique-width #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Exponential function #Graph #Interconnection Networks and Systems #Line graph #Mathematics #Partial k-tree #Pathwidth #Theory of computation #Time complexity #Tree decomposition #Tree-depth #Treewidth #Voltage graph
- Linearity of grid minors in treewidth with applications through bidimensionality
2008/01/01 by Erik D. Demaine, MohammadTaghi Hajiaghayi · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Treewidth #Combinatorics #Partial k-tree #Mathematics #1-planar graph #Pathwidth #Planar graph #Chordal graph #Clique-sum #Discrete mathematics #Tree-depth #Outerplanar graph #Bounded function #Graph minor #Graph #Line graph #Voltage graph
- Improved approximation algorithms for minimum-weight vertex separators
2005/05/22 by Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee · 3 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Combinatorics #Treewidth #Mathematics #Approximation algorithm #Vertex (graph theory) #Binary logarithm #Discrete mathematics #Bounded function #Upper and lower bounds #Tree decomposition #Planar graph #Tree-depth #Vertex cover #Pathwidth #1-planar graph #Chordal graph #Graph #Line graph
- 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
2002/01/01 by Erik D. Demaine, Mohammad Taghi Hajiaghayi, MohammadTaghi Hajiaghayi +1 · 3 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Chordal graph #Clique-sum #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph minor #Indifference graph #Line graph #Mathematics #Minor (academic) #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph
- Deciding first-order properties of locally tree-decomposable structures
2001/11/01 by Markus Frick, Martin Grohe · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #Bounded function #Mathematics #Cardinality (data modeling) #Combinatorics #Tree (set theory) #Discrete mathematics #Class (philosophy) #Tree-depth #Tree structure #Graph #1-planar graph #Binary tree #Computer science #Chordal graph
- Diameter and Treewidth in Minor-Closed Graph Families
1999/07/20 by David Eppstein · 10 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph minor #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph #math.CO #msc:05C75
- A partial k-arboretum of graphs with bounded treewidth
1998/12/01 by Hans L. Bodlaender · 24 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Artificial intelligence #Bounded function #Chordal graph #Class (philosophy) #Clique-sum #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Line graph #Mathematics #Partial k-tree #Pathwidth #Tree-depth #Treewidth #Upper and lower bounds
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
1996/12/01 by Hans L. Bodlaender · 28 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph Labeling and Dimension Problems #Treewidth #Combinatorics #Pathwidth #Tree decomposition #Partial k-tree #Mathematics #Tree-depth #Time complexity #Discrete mathematics #Path (computing) #Constant (computer programming) #Planar graph #Chordal graph #Clique-sum #1-planar graph #Graph #Algorithm #Computer science #Line graph
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
1996/09/01 by Hans L. Bodlaender, Ton Kloks · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #Treewidth #Pathwidth #Tree decomposition #Constructive #Mathematics #Combinatorics #Path (computing) #Tree-depth #Decomposition #Discrete mathematics #Time complexity #Algorithm #Graph #Computer science
- TREEWIDTH OF CIRCLE GRAPHS
1996/06/01 by Ton Kloks · 2 citations
Computer Science · Mathematics · #Interconnection Networks and Systems #Advanced Graph Theory Research #Graph Theory and Algorithms #Treewidth #Combinatorics #Partial k-tree #Circle graph #Mathematics #Block graph #Chordal graph #Outerplanar graph #Discrete mathematics #Tree-depth #Split graph #Pathwidth #Clique-sum #1-planar graph #Line graph #Graph
- Treewidth and pathwidth of permutation graphs
1993/01/01 by Hans L. Bodlaender, Ton Kloks, Dieter Kratsch · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Treewidth #Pathwidth #Combinatorics #Permutation graph #Partial k-tree #Mathematics #Tree-depth #Discrete mathematics #Chordal graph #1-planar graph #Permutation (music) #Graph #Line graph #Physics
- Approximating treewidth and pathwidth of some classes of perfect graphs
1992/01/01 by Ton Kloks, Hans L. Bodlaender · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Treewidth #Pathwidth #Combinatorics #Partial k-tree #Mathematics #Tree decomposition #1-planar graph #Discrete mathematics #Tree-depth #Chordal graph #Graph #Line graph
- Approximating treewidth, pathwidth, and minimum elimination tree height
1992/01/01 by Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Interconnection Networks and Systems #Treewidth #Combinatorics #Pathwidth #Mathematics #Tree decomposition #Vertex (graph theory) #Tree-depth #Bounded function #Discrete mathematics #Graph
- Dynamic programming on graphs with bounded treewidth
1988/01/01 by Hans L. Bodlaender · 10 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Line graph #Mathematics #Optimization and Search Problems #Partial k-tree #Pathwidth #Time complexity #Tree decomposition #Tree-depth #Treewidth