- Hardness of Metric Dimension in Graphs of Constant Treewidth
2022/07/18 by Shaohua Li, Marcin Pilipczuk · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Bounded function #Chordal graph #Combinatorics #Dimension (graph theory) #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #Line graph #Mathematics #Metric (unit) #Metric dimension #Partial k-tree #Pathwidth #Theory of computation #Tree decomposition #Treewidth #Upper and lower bounds
- 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
- Treewidth of the Kneser Graph and the Erdős-Ko-Rado Theorem
2014/02/28 by Daniel J. Harvey, David R. Wood · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Combinatorics #Treewidth #Mathematics #Discrete mathematics #Disjoint sets #Graph minor #Graph #Vertex (graph theory) #Cubic graph #Outerplanar graph #Partial k-tree #Graph power #1-planar graph #Line graph #Pathwidth #Voltage graph
- Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
2014/01/01 by Michael J. Bannister, David Eppstein · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Book embedding #Bounded function #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Crossing number (knot theory) #Discrete mathematics #Graph #Line graph #Mathematics #Minification #Partial k-tree #Pathwidth #Planarity testing #Treewidth
- 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
- Exact Algorithms for Treewidth and Minimum Fill-In
2008/01/01 by Fedor V. Fomin, Dieter Kratsch, Ioan Todinca +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Treewidth #Combinatorics #Mathematical proof #Vertex (graph theory) #Mathematics #Partial k-tree #Graph #Discrete mathematics #1-planar graph #Algorithm #Pathwidth #Chordal graph #Line graph
- Linearity of grid minors in treewidth with applications through bidimensionality
2008/01/01 by Erik D. Demaine, Mohammadtaghi Hajiaghayi, MohammadTaghi Hajiaghayi · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique-sum #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph minor #Limits and Structures in Graph Theory #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph
- Algorithms Based on the Treewidth of Sparse Graphs
2005/01/01 by Joachim Kneis, Daniel Mölle, Stefan Richter +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Interconnection Networks and Systems #Line graph #Mathematics #Partial k-tree #Pathwidth #Simple (philosophy) #Time complexity #Tree decomposition #Treewidth #Upper and lower bounds
- Bidimensional Parameters and Local Treewidth
2004/01/01 by Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #Combinatorics #Treewidth #Mathematics #Discrete mathematics #Partial k-tree #1-planar graph #Graph minor #Bounded function #Line graph #Graph #Pathwidth #Graph power
- Graph Subcolorings: Complexity and Algorithms
2003/01/01 by Jiřı́ Fiala, Klaus Jansen, Van Bang Lê +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Cograph #Discrete mathematics #Treewidth #Pathwidth #1-planar graph #Chordal graph #Split graph #Indifference graph #Planar graph #Clique-sum #Degree (music) #Partial k-tree #Bounded function #Graph #Line graph
- Approximation of pathwidth of outerplanar graphs
2002/05/01 by Hans L. Bodlaender, Fedor V. Fomin · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Chordal graph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #Line graph #Mathematics #Outerplanar graph #Partial k-tree #Pathwidth #Treewidth
- 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
2002/01/01 by Erik D. Demaine, MohammadTaghi Hajiaghayi, Mohammad Taghi 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
- Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
2002/01/01 by Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Characterization (materials science) #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constraint (computer-aided design) #Constraint satisfaction #Constraint satisfaction problem #Datalog #Discrete mathematics #Graph #Logic, Reasoning, and Knowledge #Mathematics #Partial k-tree #Pathwidth #Theoretical computer science #Time complexity #Treewidth
- Diameter and Treewidth in Minor-Closed Graph Families
1999/07/20 by David Eppstein · 11 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 · 30 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
- 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 Bodlaender, Hans L. Bodlaender, Ton Kloks +1 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithms and Data Compression #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Line graph #Mathematics #Partial k-tree #Pathwidth #Permutation (music) #Permutation graph #Physics #Tree-depth #Treewidth
- Computing treewidth and minimum fill-in: All you need are the minimal separators
1993/01/01 by Ton Kloks, T. Kloks, Hans L. Bodlaender +5 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Chordal graph #Clique-sum #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Indifference graph #Interconnection Networks and Systems #Interval graph #Line graph #Mathematics #Partial k-tree #Pathwidth #Permutation graph #Split graph #Time complexity #Treewidth
- Approximating treewidth and pathwidth of some classes of perfect graphs
1992/01/01 by Ton Kloks, Hans Bodlaender, Hans L. Bodlaender · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Line graph #Mathematics #Partial k-tree #Pathwidth #Tree decomposition #Tree-depth #Treewidth
- Dynamic programming on graphs with bounded treewidth
1988/01/01 by Hans L. Bodlaender · 11 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
- Polynomial Algorithm to Recognize a Meyniel Graph
1984/01/01 by Michel Burlet, M. Burlet, Jean Fonlupt +1 · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Indifference graph #Line graph #Mathematics #Partial k-tree #Pathwidth