A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph

Hirotoshi HONMA  Shigeru MASUYAMA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.3   pp.419-423
Publication Date: 2001/03/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithms
Keyword: 
parallel algorithm,  interval graphs,  hinge vertices,  shortest paths,  

Full Text: PDF(211KB)>>
Buy this Article




Summary: 
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 of a strongly chordal graph. Ho et al. presented a linear time algorithm for all hinge vertices of a permutation graph. 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.