On the maximum cardinality search lower bound for treewidth
type: Item
instance of: scholarly article
title: On the maximum cardinality search lower bound for treewidth
zbMATH Open document ID: 1119.05101
author: Hans L. Bodlaender
author: Arie M. C. A. Koster
published in: Discrete Applied Mathematics
publication date: 2007-07-19T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5173152
zbMATH Keywords: maximum cardinality search
zbMATH Keywords: treewidth
zbMATH Keywords: lower bounds
zbMATH Keywords: planar graphs
zbMATH Keywords: graph algorithms
describes a project that uses: Treewidthlib
MaRDI profile type: Publication
full work available at URL: j.dam.2007.02.004
OpenAlex ID: W2159851316
cites work: Experimental and Efficient Algorithms
cites work: A sufficiently fast algorithm for finding close to optimal clique trees
cites work: Algorithms – ESA 2005
cites work: Safe separators for treewidth
cites work: Contraction and Treewidth Lower Bounds
cites work: Q4426346
cites work: Heuristic and metaheuristic methods for computing graph treewidth
cites work: Q4414495
cites work: Safe reduction rules for weighted treewidth
cites work: Treewidth: computational experiments
cites work: Solving partial constraint satisfaction problems with tree decomposition
cites work: Q4734791
cites work: A New Lower Bound for Tree-Width Using Maximum Cardinality Search
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: A spectral lower bound for the treewidth of a graph and its consequences
cites work: Girth and treewidth
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
Wikidata QID: Q59567777
DOI: 10.1016/J.DAM.2007.02.004
DBLP publication ID: journals/dam/BodlaenderK07
Recommended article: Graph-Theoretic Concepts in Computer Science
Recommended article: A New Lower Bound for Tree-Width Using Maximum Cardinality Search
Recommended article: A lower bound for treewidth and its consequences
Recommended article: Graph searching and a min-max theorem for tree-width
Recommended article: Treewidth computations. II. Lower bounds
Recommended article: On treewidth approximations
Recommended article: Upper Bounds for Maximally Greedy Binary Search Trees
Recommended article: A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
Recommended article: On Exact Algorithms for Treewidth
Recommended article: Lower bounds on the size of general branch-and-bound trees
description: scientific article; zbMATH DE number 5173152