A Parallel Algorithm for Finding All Hinge Vertices of a Trapezoid Graph(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 [3].

• 社団法人電子情報通信学会の論文
• 2002-05-01

著者

• Masuyama Shigeru

  The Author Is With The Department Of Knowledge-based Information Engineering Toyohashi University Of

• HONMA Hirotoshi

  The author is with the Department of Information Engineering, Kushiro National College of Technology

• Honma H

  The Author Is With The Department Of Information Engineering Kushiro National College Of Technology

関連論文

• A Parallel Algorithm for Finding All Hinge Vertices of a Trapezoid Graph(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク