A linear time algorithm to recognize circular permutation graphs

DOI<171::AID-NET1>3.0.CO;2-F 10.1002/(SICI)1097-0037(199605)27:3<171::AID-NET1>3.0.CO;2-FzbMath0853.05073OpenAlexW2009049598MaRDI QIDQ4887747

R. Sritharan

Publication date: 9 December 1996

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199605)27:3<171::aid-net1>3.0.co;2-f

zbMATH Keywords

recognitionlinear timepartial orderspermutation graphs

Mathematics Subject Classification ID

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

Related Items (6)

Graph classes with structured neighborhoods and algorithmic applications ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ Succinct permutation graphs ⋮ Switching to Hedgehog-Free Graphs Is NP-Complete ⋮ On Switching to H‐Free Graphs ⋮ Modular decomposition and transitive orientation

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