Treewidth lower bounds with brambles
type: Item
instance of: scholarly article
title: Treewidth lower bounds with brambles
zbMATH Open document ID: 1138.68065
author: Hans L. Bodlaender
author: Alexander Grigoriev
author: Arie M. C. A. Koster
published in: Algorithmica
publication date: 2008-05-27T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5279055
zbMATH Keywords: Treewidth
zbMATH Keywords: Lower bound
zbMATH Keywords: Bramble
zbMATH Keywords: Planar graph
zbMATH Keywords: Grid minor
zbMATH Keywords: Approximation algorithm
Wikidata QID: Q59567755
describes a project that uses: Treewidthlib
MaRDI profile type: Publication
full work available at URL: s00453-007-9056-z
OpenAlex ID: W2113901576
cites work: Q3056948
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Q4792909
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Safe separators for treewidth
cites work: Algorithms – ESA 2004
cites work: Contraction and Treewidth Lower Bounds
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: Q4426346
cites work: Heuristic and metaheuristic methods for computing graph treewidth
cites work: Tour merging via branch-decomposition
cites work: Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
cites work: Highly connected sets and the excluded grid theorem
cites work: Automata, Languages and Programming
cites work: Q4198056
cites work: Planar branch decompositions. I: The ratcatcher
cites work: Planar branch decompositions. II: The cycle method
cites work: Efficient Planarity Testing
cites work: Treewidth: computational experiments
cites work: Experimental and Efficient Algorithms
cites work: A New Lower Bound for Tree-Width Using Maximum Cardinality Search
cites work: The Structure and Number of Obstructions to Treewidth
cites work: Q4352948
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Quickly excluding a planar graph
cites work: Graph searching and a min-max theorem for tree-width
cites work: Call routing and the ratcatcher
cites work: \(E_{11}\) and M theory
DBLP publication ID: journals/algorithmica/BodlaenderGK08
DOI: 10.1007/S00453-007-9056-Z
description: scientific article; zbMATH DE number 5279055