Finding the set of all hinge vertices for strongly chordal graphs in linear time

Let V(G) be the vertex set of a graph G=(V,E), and let G-u be the subgraph induced by the vertex set V(G)-{u}. A vertex u is an element of V(G) is said to be a hinge vertex of G if and only if there exist two vertices x,y is an element of V(G-u) such that d(G-u)(x,y) > d(G)(x,y), where d(G)(x,y) is the distance (the length of a shortest path) between x and y in G. In this paper, based on the breadth-first search technique, an O(n+e) time algorithm is proposed for finding the set of all hinge vertices of a strongly chordal graph when a strong elimination ordering is given. (C) Elsevier Science Inc. 1997.