An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph

Hirotoshi HONMA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.1   pp.383-391
Publication Date: 2008/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.1.383
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
parallel algorithms,  circular-arc graphs,  hinge vertices,  network reliability,  

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

Let G =(V, E) be an undirected simple graph with uV. 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 is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n/log n) processors on EREW PRAM for finding all hinge vertices of a circular-arc graph.