A spectral lower bound for the treewidth of a graph and its consequences
From MaRDI portal
Publication:1014419
DOI10.1016/S0020-0190(03)00286-2zbMath1161.68647OpenAlexW2052803891MaRDI QIDQ1014419
L. Sunil Chandran, C. R. Subramanian
Publication date: 28 April 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00286-2
Related Items (6)
Random subgraphs of the 2D Hamming graph: The supercritical phase ⋮ Differential geometric treewidth estimation in adiabatic quantum computation ⋮ A combinatorial Li-Yau inequality and rational points on curves ⋮ Treewidth computations. II. Lower bounds ⋮ The carving-width of generalized hypercubes ⋮ On the maximum cardinality search lower bound for treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Spectral partitioning works: planar graphs and finite element meshes
- Graph minors. I. Excluding a forest
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Eigenvalues and expanders
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Eigenvalues, diameter, and mean distance in graphs
- Treewidth for graphs with small chordality
- Graph minors. II. Algorithmic aspects of tree-width
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: A spectral lower bound for the treewidth of a graph and its consequences
