For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph
Hirotoshi HONMA Shigeru MASUYAMA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/03/01
Print ISSN: 0916-8532
Type of Manuscript: LETTER
parallel algorithm, interval graphs, hinge vertices, shortest paths,
Full Text: PDF(211KB)>>
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.