Fast recognition of doubled graphs

DOI10.1016/J.TCS.2013.11.020MaRDI QIDQ385965zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray

Publication date 13 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.11.020

zbMATH Keywords

double split graphrecognition

Mathematics Subject Classification ID

Perfect graphs (05C17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Forbidden induced subgraphs of double-split graphs
• Split-neighbourhood graphs and the strong perfect graph conjecture
• Recognizing Perfect 2-Split Graphs
• scientific article; zbMATH DE number 1009511
• A note on the recognition of bisplit graphs

Cites work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Forbidden induced subgraphs of double-split graphs
• Geometric algorithms and combinatorial optimization
• Introduction to algorithms
• The splittance of a graph
• The strong perfect graph theorem

Cited in

(2)

• Linear-time recognition of double-threshold graphs
• Star covers and star partitions of double-split graphs

This page was built for publication: Fast recognition of doubled graphs

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