Treewidth computations. II. Lower bounds
From MaRDI portal
Publication:549673
DOI10.1016/J.IC.2011.04.003zbMATH Open1220.68071OpenAlexW1990761146WikidataQ59567635 ScholiaQ59567635MaRDI QIDQ549673FDOQ549673
Authors: Hans L. Bodlaender, Arie M. C. A. Koster 
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
Recommendations
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph designs and isomorphic decomposition (05C51)
Cites Work
- Network flows. Theory, algorithms, and applications.
- Graph theory
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Call routing and the ratcatcher
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On Exact Algorithms for Treewidth
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Graph minors. II. Algorithmic aspects of tree-width
- 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
- Boxicity and treewidth
- Treewidth and Pathwidth of Permutation Graphs
- Treewidth computations. I: Upper bounds
- Planar branch decompositions. I: The ratcatcher
- A spectral lower bound for the treewidth of a graph and its consequences
- The Structure and Number of Obstructions to Treewidth
- Girth and treewidth
- Contraction and Treewidth Lower Bounds
- Necessary edges in \(k\)-chordalisations of graphs
- Experimental and Efficient Algorithms
- Treewidth lower bounds with brambles
- A combinatorial optimization algorithm for solving the branchwidth problem
- Algorithms – ESA 2004
- Title not available (Why is that?)
- A New Lower Bound for Tree-Width Using Maximum Cardinality Search
- Title not available (Why is that?)
- Constant-degree graph expansions that preserve treewidth
- On the maximum cardinality search lower bound for treewidth
Cited In (42)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Treewidth versus clique number. II: Tree-independence number
- Title not available (Why is that?)
- Courcelle's theorem -- a game-theoretic approach
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- Experimental and Efficient Algorithms
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Maintaining range trees is secondary memory. Part II: Lower bounds
- Treewidth lower bounds with brambles
- Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
- On the maximum cardinality search lower bound for treewidth
- Finding good decompositions for dynamic programming on dense graphs
- Treewidth distance on phylogenetic trees
- Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
- Algorithms – ESA 2005
- Computing treewidth on the GPU
- Title not available (Why is that?)
- Treewidth computations. I: Upper bounds
- Lower Bounds for QBFs of Bounded Treewidth
- Adiabatic quantum programming: minor embedding with hard faults
- Locating Eigenvalues of Symmetric Matrices - A Survey
- Treewidth and the Computational Complexity of MAP Approximations
- An Experimental Study of the Treewidth of Real-World Graph Data
- A combinatorial Li-Yau inequality and rational points on curves
- Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs
- Treewidth of display graphs: bounds, brambles and applications
- Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width
- A managed Bayesian risk approach for decision making alternatives
- Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
- Title not available (Why is that?)
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- A lower bound for tree resolution
- An improved spectral lower bound of treewidth
- Graphs of gonality three
- Recognizing hyperelliptic graphs in polynomial time
- Minimum size tree-decompositions
- Algorithms – ESA 2004
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- A sequential reduction method for inference in generalized linear mixed models
- Contraction and Treewidth Lower Bounds
- A New Lower Bound for Tree-Width Using Maximum Cardinality Search
- On making a distinguished vertex of minimum degree by vertex deletion
Uses Software
This page was built for publication: Treewidth computations. II. Lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q549673)
