Let Gs=(Vs, Es) be a simple connected graph. A vertex v ∈ Vs is an articulation vertex if deletion of v and its incident edges from Gs disconnects the graph into at least two connected components. Finding all articulation vertices of a given graph is called the articulation vertex problem. A vertex u ∈ Vs is called a hinge vertex if there exist any two vertices x and y in Gs whose distance increase when u is removed. Finding all hinge vertices of a given graph is called the hinge vertex problem. These problems can be applied to improve the stability and robustness of communication network systems. In this paper, we propose linear time algorithms for the articulation vertex problem and the hinge vertex problem of circular permutation graphs.

Let G =(V, E) be an undirected simple graph with u ∈ V. 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.

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.

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.