A four-sweep LBFS recognition algorithm for interval graphs

MaRDI QIDQ5167721zbMATH OpenFDO

Authors Peng Li, Yaokun Wu

Publication date 1 July 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2066/0.html

zbMATH Keywords

interval graphchordal graphrecognition algorithminterval representationlexicographic breadth-first searchperfect ordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• The LBFS structure and recognition of interval graphs
• Simple linear time recognition of unit interval graphs
• A linear-time algorithm for proper interval graph recognition
• scientific article; zbMATH DE number 176590

Cited in

(11)

• Robinsonian matrices: recognition challenges
• A five-element transformation monoid on labelled trees
• Maximal neighborhood search and rigid interval graphs
• Graph classes and forbidden patterns on three vertices
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Graph searches and their end vertices
• A simple linear time algorithm to solve the MIST problem on interval graphs
• The LexCycle on \(\overline{P_2\cup P_3} \)-free cocomparability graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• Semi-proper interval graphs
• The LBFS structure and recognition of interval graphs

This page was built for publication: A four-sweep LBFS recognition algorithm for interval graphs

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