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

DOI10.1016/J.ENDM.2015.07.029zbMATH Open1347.05162OpenAlexW2213949098MaRDI QIDQ324769FDOQ324769

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

Publication date 17 October 2016

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

zbMATH Keywords

graph decompositionrecognition algorithmschordless graphspropeller-subgraph-free graphsSPQR-tree

Mathematics Subject Classification ID

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

Recommendations

• Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
• scientific article; zbMATH DE number 177843
• Canonical representations of partial 2- and 3-trees
• scientific article; zbMATH DE number 2080088
• scientific article; zbMATH DE number 2038697

Cites Work

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Dividing a Graph into Triconnected Components
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Minimally 2-connected graphs.
• On Minimal Blocks
• On graphs with no induced subdivision of \(K_4\)
• On induced subgraphs of a block
• On-Line Planarity Testing

Cited In (3)

• Title not available (Why is no real title available?)
• Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
• Title not available (Why is no real title available?)

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

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