On tree width, bramble size, and expansion
From MaRDI portal
Publication:2519023
DOI10.1016/j.jctb.2008.06.004zbMath1205.05049OpenAlexW1973819999MaRDI QIDQ2519023
Publication date: 21 January 2009
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2008.06.004
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items (36)
Treewidth distance on phylogenetic trees ⋮ Constructing Brambles ⋮ Target Set Selection in Dense Graph Classes ⋮ Constant Congestion Brambles in Directed Graphs ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Systematic and deterministic graph minor embedding for Cartesian products of graphs ⋮ Connecting Width and Structure in Knowledge Compilation (Extended Version) ⋮ Lower bounds on the mim-width of some graph classes ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ Constant Congestion Brambles ⋮ Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings ⋮ Graphs of linear growth have bounded treewidth ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Parameterized Counting and Cayley Graph Expanders ⋮ Parameters Tied to Treewidth ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Excluded Forest Minors and the Erdős–Pósa Property ⋮ The Parameterized Complexity of Finding Point Sets with Hereditary Properties ⋮ A branch-and-price-and-cut method for computing an optimal bramble ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs ⋮ Layouts of Expander Graphs ⋮ The treewidth of line graphs ⋮ Parameterized counting of partially injective homomorphisms ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Connecting knowledge compilation classes and width parameters ⋮ Treewidth of the Line Graph of a Complete Graph ⋮ Isoperimetric numbers of randomly perturbed intersection graphs ⋮ Tree decompositions and social graphs ⋮ On vertex rankings of graphs and its relatives ⋮ The treewidth of 2-section of hypergraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Graph searching and a min-max theorem for tree-width
- Parametrized complexity theory.
- Expander graphs and their applications
- Improved approximation algorithms for minimum-weight vertex separators
This page was built for publication: On tree width, bramble size, and expansion
