Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs

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

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

 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
Consider a simple undirected graph G = (V,E) with vertex set V and edge set E. Let Gu be a subgraph induced by the vertex set V{u}. The distance δ_{G}(x,y) is defined as the length of the shortest path between vertices x and y in G. The vertex u ∈ V is a hinge vertex if there exist two vertices x,y ∈ V{u} such that δ_{Gu}(x,y)>δ_{G}(x,y). Let U be a set consisting of all hinge vertices of G. The neighborhood of u is the set of all vertices adjacent to u and is denoted by N(u). We define d(u) = max{δ_{Gu}(x,y)  δ</i>_{Gu}(x,y)>δ_{G}(x,y),x,y ∈ N(u)} for u ∈ U as detour degree of u. A maximum detour hinge vertex problem is to find a hinge vertex u with maximum d(u) in G. In this paper, we proposed an algorithm to find the maximum detour hinge vertex on an interval graph that runs 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 E97.A (6), 13651369, 2014
The Institute of Electronics, Information and Communication Engineers
 Tweet
Keywords
Details 詳細情報について

 CRID
 1390001206310277760

 NII Article ID
 130004770864

 ISSN
 17451337
 09168508

 Text Lang
 en

 Data Source

 JaLC
 Crossref
 CiNii Articles
 KAKEN

 Abstract License Flag
 Disallowed