Treewidth computations. II. Lower bounds
From MaRDI portal
Publication:549673
DOI10.1016/j.ic.2011.04.003zbMath1220.68071OpenAlexW1990761146WikidataQ59567635 ScholiaQ59567635MaRDI QIDQ549673
Arie M. C. A. Koster, Hans L. Bodlaender
Publication date: 18 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.04.003
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph designs and isomorphic decomposition (05C51)
Related Items
Finding Good Decompositions for Dynamic Programming on Dense Graphs, As Time Goes By: Reflections on Treewidth for Temporal Graphs, Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs, Treewidth distance on phylogenetic trees, Fixed-Parameter Tractability of Treewidth and Pathwidth, Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width, Courcelle's theorem -- a game-theoretic approach, Treewidth versus clique number. II: Tree-independence number, Locating Eigenvalues of Symmetric Matrices - A Survey, Unnamed Item, Practical algorithms for MSO model-checking on tree-decomposable graphs, Adiabatic quantum programming: minor embedding with hard faults, Minimum size tree-decompositions, \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions, On making a distinguished vertex of minimum degree by vertex deletion, Treewidth computations. I: Upper bounds, A combinatorial Li-Yau inequality and rational points on curves, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, A sequential reduction method for inference in generalized linear mixed models, Graphs of gonality three, Recognizing hyperelliptic graphs in polynomial time, An Experimental Study of the Treewidth of Real-World Graph Data, Treewidth of display graphs: bounds, brambles and applications, Computing treewidth on the GPU, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A combinatorial optimization algorithm for solving the branchwidth problem
- Constant-degree graph expansions that preserve treewidth
- Girth and treewidth
- Treewidth lower bounds with brambles
- Treewidth computations. I: Upper bounds
- On the maximum cardinality search lower bound for treewidth
- A spectral lower bound for the treewidth of a graph and its consequences
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- A partial k-arboretum of graphs with bounded treewidth
- Call routing and the ratcatcher
- Necessary edges in \(k\)-chordalisations of graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Boxicity and treewidth
- Planar Branch Decompositions I: The Ratcatcher
- The Structure and Number of Obstructions to Treewidth
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Characterization and Recognition of Partial 3-Trees
- Graph minors. II. Algorithmic aspects of tree-width
- A New Lower Bound for Tree-Width Using Maximum Cardinality Search
- Treewidth and Pathwidth of Permutation Graphs
- Contraction and Treewidth Lower Bounds
- On Exact Algorithms for Treewidth
- Algorithms – ESA 2004
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Experimental and Efficient Algorithms
