A linear time algorithm to recognize circular permutation graphs

DOI10.1002/(SICI)1097-0037(199605)27:3%3C171::AID-NET1%3E3.0.CO;2-FzbMATH Open0853.05073OpenAlexW2009049598MaRDI QIDQ4887747FDOQ4887747

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

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

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)

Cited In (8)

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

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)