For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Linear Time Algorithms for Finding Articulation and Hinge Vertices of Circular Permutation GraphsHirotoshi HONMA  Kodai ABE  Yoko NAKAJIMA  Shigeru MASUYAMA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.3   pp.419-425Publication Date: 2013/03/01 Online ISSN: 1745-1361 DOI: 10.1587/transinf.E96.D.419 Print ISSN: 0916-8532Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)Category: Keyword: design and analysis of algorithms,  articulation vertices,  hinge vertices,  circular permutation graphs,  Full Text: PDF(468.2KB)>> Buy this Article Summary:  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.