The nonexistence of reduction rules giving an embedding into a \(k\)-tree

DOI10.1016/0166-218X(94)90023-XzbMath0809.05034WikidataQ127883899 ScholiaQ127883899MaRDI QIDQ1336627

Jens Lagergren

Publication date: 1 February 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

embeddingtreewidthlinear time algorithmstree-decomposition\(k\)-tree embedding problemtriggered reduction rule

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (2)

Canonical representations of partial 2- and 3-trees ⋮ A partial k-arboretum of graphs with bounded treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterization of partial 3-trees in terms of three structures
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On simple characterizations of k-trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Linear-time computation of optimal subgraphs of decomposable graphs

This page was built for publication: The nonexistence of reduction rules giving an embedding into a \(k\)-tree