A Parallel Algorithm for Finding All Hinge Vertices of a Trapezoid Graph

Hirotoshi HONMA  Shigeru MASUYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.5   pp.1031-1040
Publication Date: 2002/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
parallel algorithm,  trapezoid graphs,  hinge vertices,  network reliability,  

Full Text: PDF(688KB)>>
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 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) processors on CREW PRAM for finding all hinge vertices of a trapezoid graph.