Graph contraction pattern matching for graphs of bounded treewidth

MaRDI QIDQ3459921zbMATH OpenFDO

Authors Takashi Yamada, Takayoshi Shoudai

Publication date 11 January 2016

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient pattern matching on graph patterns of bounded treewidth
• On contracting graphs to fixed pattern graphs
• The computational complexity of graph contractions II: Two tough polynomially solvable cases
• The computational complexity of graph contractions I: Polynomially solvable and NP-complete cases
• The complexity of graph contractions.

Cited in

(4)

• Patterns with Bounded Treewidth
• Contraction obstructions for treewidth
• Bounded contractions of full trees
• Efficient pattern matching on graph patterns of bounded treewidth

This page was built for publication: Graph contraction pattern matching for graphs of bounded treewidth

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