Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs

DOI Web Site 3 Citations 15 References Open Access
  • 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

Description

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 u ∈ V is a hinge vertex if there exist two vertices x,y ∈ V-{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,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(n2) time, where n is the number of vertices in the graph.

Journal

Citations (3)*help

See more

References(15)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top