Algorithm for Identifying the Maximum Detour Hinge Vertices of a Permutation Graph

 HONMA Hirotoshi
 Department of Information Engineering, National Institute of Technology, Kushiro College

 NAKAJIMA Yoko
 Department of Information Engineering, National Institute of Technology, Kushiro College

 IGARASHI Yuta
 Electronic Information System Engineering Course, Kushiro National College of Technology

 MASUYAMA Shigeru
 Department of Computer Science and Engineering, Toyohashi University of Technology
Abstract
A hinge vertex is a vertex in an undirected graph such that there exist two vertices whose removal makes the distance between them longer than before. Identifying hinge vertices in a graph can help detect critical nodes in communication network systems, which is useful for making them more stable. For finding them, an O(n^{3}) time algorithm was developed for a simple graph, and, linear time algorithms were developed for interval and permutation graphs, respectively. Recently, the maximum detour hinge vertex problem is defined by Honma et al. For a hinge vertex u in a graph, the detour degree of u is the largest value of distance between any pair of x and y (x and y are adjacent to u) by removing u. A hinge vertex with the largest detour degree in G is defined as the maximum detour hinge vertex of G. This problem is motivated by practical applications, such as network stabilization with a limited cost, i.e., by enhancing the reliability of the maximum detour hinge vertex, the stability of the network is much improved. We previously developed an O(n^{2}) time algorithm for solving this problem on an interval graph. In this study, we propose an algorithm that identifies the maximum detour hinge vertex on a permutation graph in O(n^{2}) time, where n is the number of vertices in the graph.
Journal

 IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A (6), 11611167, 2015
The Institute of Electronics, Information and Communication Engineers
 Tweet
Keywords
Details 詳細情報について

 CRID
 1390001206310824576

 NII Article ID
 130005071825

 ISSN
 17451337
 09168508

 Text Lang
 en

 Data Source

 JaLC
 Crossref
 CiNii Articles
 KAKEN

 Abstract License Flag
 Disallowed