A linear time algorithm for finding all hinge vertices of a permutation graph

DOI10.1016/0020-0190(96)00092-0zbMath0900.68331OpenAlexW2091437869MaRDI QIDQ671396

Ting-Yem Ho, Yue-Li Wang, Ming-Tsan Juan

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00092-0

zbMATH Keywords

AlgorithmsHinge verticesNeighborhoodPermutation graphsShortest paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The recognition of geodetically connected graphs ⋮ Erratum and addendum to ``A linear time algorithm for finding all hinge vertices of a permutation graph ⋮ Evolution of cooperation for multiple mutant configurations on all regular graphs with \(N \leq 14\) players ⋮ Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs ⋮ An efficient distributed algorithm for finding all hinge vertices in networks

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizations of strongly chordal graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Permutation Graphs and Transitive Graphs