Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs

DOI Web Site 被引用文献3件 参考文献15件 オープンアクセス
  • 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

説明

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.

収録刊行物

被引用文献 (3)*注記

もっと見る

参考文献 (15)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ