- 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
- A Single-Exponential Time 2-Approximation Algorithm for Treewidth
2022/02/01 by Tuukka Korhonen · 2 citations
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
- 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
- Inapproximability of Treewidth and Related Problems
2014/04/06 by Yuhuai Wu, Per Austrin, Toniann Pitassi +1 · 1 citation
Computer Science · Mathematics · #Bayesian Modeling and Causal Inference #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Treewidth #Partial k-tree #Pathwidth #Combinatorics #Tree-depth #Graphical model #Tree decomposition #Mathematics #Chordal graph #Discrete mathematics #Computer science #Graph #1-planar graph #Line graph #Artificial intelligence
- 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
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
2008/01/01 by Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Combinatorics #Mathematics #Treewidth #Approximation algorithm #Vertex (graph theory) #Binary logarithm #Upper and lower bounds #Planar graph #Discrete mathematics #Tree decomposition #Exponential time hypothesis #Time complexity #Graph #Pathwidth #Line graph
- Improved approximation algorithms for minimum-weight vertex separators
2005/05/22 by Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee · 4 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
- 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
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
1997/11/01 by Jan Arne Telle, Andrzej Proskurowski · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems #Treewidth #Mathematics #Vertex (graph theory) #Algorithm #Bounded function #Time complexity #Tree decomposition #Vertex cover #Combinatorics #Discrete mathematics #Graph #Pathwidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
1996/12/01 by Hans L. Bodlaender · 32 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 #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constructive #Decomposition #Discrete mathematics #Graph #Interconnection Networks and Systems #Mathematics #Path (computing) #Pathwidth #Time complexity #Tree decomposition #Tree-depth #Treewidth
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
1996/01/01 by Jens Lagergren · 5 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Binary tree #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Decomposition #Discrete mathematics #Gomory–Hu tree #Graph #Interconnection Networks and Systems #K-ary tree #Mathematics #Parallel algorithm #Pathwidth #Time complexity #Tree (set theory) #Tree decomposition #Tree structure
- Tree-width and path-width of comparability graphs of interval orders
1995/01/01 by R. Garbe, Renate Garbe · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Comparability #Complexity and Algorithms in Graphs #Computer science #Constructive #Discrete mathematics #Formal Methods in Verification #Graph #Interval (graph theory) #Interval graph #Line graph #Mathematics #Path (computing) #Path length #Pathwidth #Tree (set theory) #Tree decomposition
- Tree-width, path-width, and cutwidth
1993/05/01 by Ephraim Korach, Nir Solel · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Computer science #Constant (computer programming) #Discrete mathematics #Graph #Graph theory and applications #Interconnection Networks and Systems #Mathematical analysis #Mathematics #Path (computing) #Pathwidth #Tree (set theory) #Tree decomposition #Upper and lower bounds
- Approximating treewidth and pathwidth of some classes of perfect graphs
1992/01/01 by Ton Kloks, Hans L. Bodlaender, Hans 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
- 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 #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Interconnection Networks and Systems #Mathematics #Pathwidth #Tree decomposition #Tree-depth #Treewidth #Vertex (graph theory)
- 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
- Complexity of Finding Embeddings in a k-Tree
1987/04/01 by Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski · 48 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Mathematics #Combinatorics #Discrete mathematics #Time complexity #Graph #Gomory–Hu tree #Vertex (graph theory) #Tree decomposition #Bounded function #Feedback vertex set #K-ary tree #Line graph #Pathwidth #Tree structure #Binary tree