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

DOI10.1007/3-540-61228-9_106zbMATH Open1412.68161OpenAlexW1506863176MaRDI QIDQ4645295FDOQ4645295

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

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

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)

Cites Work

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

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)