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 . 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 .
|Number of pages||5|
|Journal||IEICE Transactions on Information and Systems|
|Publication status||Published - Mar 2001|
- Hinge vertices
- Interval graphs
- Parallel algorithms
- Shortest paths