Using SPQR-trees to speed up recognition algorithms based on 2-cutsets

DOI10.1016/j.dam.2017.01.009zbMath1387.05050OpenAlexW2587567120MaRDI QIDQ1752488

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

Publication date: 24 May 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.01.009

zbMATH Keywords

recognition algorithmschordless graphsSPQR-treeslinear-time complexitypropeller-free graphs

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Edge-colouring and total-colouring chordless graphs
• On graphs with no induced subdivision of \(K_4\)
• Chromatic index of graphs with no cycle with a unique chord
• A structural characterization of planar combinatorial graphs
• On induced subgraphs of a block
• On-Line Planarity Testing
• 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 recognition algorithms based on 2-cutsets