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

Recommendations

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

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)

Cites Work

• On graphs with no induced subdivision of \(K_4\)
• On-Line Planarity Testing
• Minimally 2-connected graphs.
• On Minimal Blocks
• Dividing a Graph into Triconnected Components
• On induced subgraphs of a block
• 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

Cited In (2)

• Title not available (Why is that?)
• Title not available (Why is that?)

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)