# 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 G-u 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 uV is a hinge vertex if there exist two vertices x,yV-{u} such that δG-u(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{δG-u(x,y) | δ</i>G-u(x,y)G(x,y),x,yN(u)} for uU 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(n2) time, where n is the number of vertices in the graph.

See more

See more

See more