A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths

DOI10.1007/3-540-61228-9_106MaRDI QIDQ4645295zbMATH OpenOpenAlexFDO

Authors Stefan Arnborg, Andrzej Proskurowski

Publication date 10 January 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61228-9_106

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75) Grammars and rewriting systems (68Q42)

Recommendations

• An algebraic theory of graph reduction
• Reduction algorithms for graphs of small treewidth
• scientific article; zbMATH DE number 177426
• scientific article; zbMATH DE number 4008410
• scientific article; zbMATH DE number 219268

Cites work

• scientific article; zbMATH DE number 58315 (Why is no real title available?)
• scientific article; zbMATH DE number 3639689 (Why is no real title available?)
• scientific article; zbMATH DE number 512967 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• An algebraic theory of graph reduction
• Canonical representations of partial 2- and 3-trees
• Combinatorial algorithms on a class of graphs
• Easy problems for tree-decomposable graphs
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph expressions and graph rewritings
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Obstruction set isolation for the gate matrix layout problem
• On simple characterizations of k-trees
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Recognition of Series Parallel Digraphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(4)

• Treewidth-two graphs as a free algebra
• An algebraic theory of graph reduction
• A partial k-arboretum of graphs with bounded treewidth
• A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata

This page was built for publication: A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645295)