A linear time algorithm to recognize circular permutation graphs

DOI10.1002/(SICI)1097-0037(199605)27:3%3C171::AID-NET1%3E3.0.CO;2-FMaRDI QIDQ4887747zbMATH OpenOpenAlexFDO

Authors R. Sritharan

Publication date 9 December 1996

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199605)27:3%3C171::aid-net1%3E3.0.co;2-f

zbMATH Keywords

partial ordersrecognitionpermutation graphslinear time

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Recommendations

• Circular permutation graph family with applications
• Linear-time recognition of circular-arc graphs
• A simpler linear-time recognition of circular-arc graphs
• Recognizing circle graphs in polynomial time
• A Simpler Linear-Time Recognition of Circular-Arc Graphs

Cited in

(8)

• Circular permutation graph family with applications
• Succinct permutation graphs
• Graph classes with structured neighborhoods and algorithmic applications
• On Switching to H‐Free Graphs
• A linear time algorithm for finding all hinge vertices of a permutation graph
• Switching to hedgehog-free graphs is NP-complete
• Partial and simultaneous transitive orientations via modular decompositions
• Modular decomposition and transitive orientation

This page was built for publication: A linear time algorithm to recognize circular permutation graphs

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