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

DOI10.1016/J.ENDM.2015.07.029MaRDI QIDQ324769zbMATH OpenOpenAlexFDO

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

chordless graphsgraph decompositionpropeller-subgraph-free graphsrecognition algorithmsSPQR-tree

Mathematics Subject Classification ID

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

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 graphs with no induced subdivision of \(K_4\)
• On induced subgraphs of a block
• On Minimal Blocks
• On-Line Planarity Testing

Cited in

(3)

• Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
• scientific article; zbMATH DE number 177843 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (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)