A parallel algorithm for finding all hinge vertices of an interval graph

Hirotoshi Honma, Shigeru Masuyama

Research output: Contribution to journalLetterpeer-review

8 Citations (Scopus)

Abstract

If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph can be used to identify critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In general, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. For instance, Chang et al. presented an O(n + m) time algorithm for finding all hinge vertices on a strongly chordal graph [1]. Ho et al. presented a linear time algorithm for all hinge vertices of a permutation graph [3]. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of an interval graph [4].

Original languageEnglish
Pages (from-to)419-423
Number of pages5
JournalIEICE Transactions on Information and Systems
VolumeE84-D
Issue number3
Publication statusPublished - Mar 2001

Keywords

  • Hinge vertices
  • Interval graphs
  • Parallel algorithms
  • Shortest paths

Fingerprint Dive into the research topics of 'A parallel algorithm for finding all hinge vertices of an interval graph'. Together they form a unique fingerprint.

Cite this