Using SPQR-trees to speed up algorithms based on 2-cutset decompositions

DOI10.1016/j.endm.2015.07.029zbMath1347.05162OpenAlexW2213949098MaRDI QIDQ324769

H. B. de Macêdo Filho, Zhentao Li, Celina M. Herrera de Figueiredo, Nicolas Trotignon, Raphael C. S. Machado

Publication date: 17 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.029

zbMATH Keywords

recognition algorithmsgraph decompositionchordless graphspropeller-subgraph-free graphsSPQR-tree

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Cites Work

• On graphs with no induced subdivision of \(K_4\)
• On induced subgraphs of a block
• On-Line Planarity Testing
• Dividing a Graph into Triconnected Components
• Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Minimally 2-connected graphs.
• On Minimal Blocks

This page was built for publication: Using SPQR-trees to speed up algorithms based on 2-cutset decompositions