IEICE TRANSACTIONS on Fundamentals
Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs
Summary :
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) | δ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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1365-1369
- Publication Date
- 2014/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.1365
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Hirotoshi HONMA
Kushiro National College of Technology
Yoko NAKAJIMA
Kushiro National College of Technology
Yuta IGARASHI
Kushiro National College of Technology
Shigeru MASUYAMA
Toyohashi University of Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hirotoshi HONMA, Yoko NAKAJIMA, Yuta IGARASHI, Shigeru MASUYAMA, "Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1365-1369, June 2014, doi: 10.1587/transfun.E97.A.1365.
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 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) | δ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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1365/_p
Copy
@ARTICLE{e97-a_6_1365,
author={Hirotoshi HONMA, Yoko NAKAJIMA, Yuta IGARASHI, Shigeru MASUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs},
year={2014},
volume={E97-A},
number={6},
pages={1365-1369},
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 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) | δ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.},
keywords={},
doi={10.1587/transfun.E97.A.1365},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Algorithm for Finding Maximum Detour Hinge Vertices of Interval Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1365
EP - 1369
AU - Hirotoshi HONMA
AU - Yoko NAKAJIMA
AU - Yuta IGARASHI
AU - Shigeru MASUYAMA
PY - 2014
DO - 10.1587/transfun.E97.A.1365
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - 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) | δ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.
ER -
English
