Algorithm for Solving the Detour Hinge Vertex Problem on Circular-arc Graphs
Article Sidebar
Main Article Content
Abstract
Consider a simple undirected graph with vertex set
and edge set
. Let
be a subgraph induced by the vertex set
. The distance
is defined as the length of the shortest path between vertices
and
in
. The vertex
is a hinge vertex if there are two vertices
such that
. Let
be a set consisting of all hinge vertices of
. The neighborhood of
, denoted by
, is the set of all vertices adjacent to
. We define the detour degree of
as
for
. The detour hinge vertex problem aims to determine the hinge vertex
that maximizes
in
. In this study, we proposed an efficient algorithm for solving the detour hinge vertex problem on circular-arc graphs that runs in
time, where
is the number of vertices in the graph.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Article Accepting Policy
The editorial board of Thai-Nichi Institute of Technology is pleased to receive articles from lecturers and experts in the fields of business administration, languages, engineering and technology written in Thai or English. The academic work submitted for publication must not be published in any other publication before and must not be under consideration of other journal submissions. Therefore, those interested in participating in the dissemination of work and knowledge can submit their article to the editorial board for further submission to the screening committee to consider publishing in the journal. The articles that can be published include solely research articles. Interested persons can prepare their articles by reviewing recommendations for article authors.
Copyright infringement is solely the responsibility of the author(s) of the article. Articles that have been published must be screened and reviewed for quality from qualified experts approved by the editorial board.
The text that appears within each article published in this research journal is a personal opinion of each author, nothing related to Thai-Nichi Institute of Technology, and other faculty members in the institution in any way. Responsibilities and accuracy for the content of each article are owned by each author. If there is any mistake, each author will be responsible for his/her own article(s).
The editorial board reserves the right not to bring any content, views or comments of articles in the Journal of Thai-Nichi Institute of Technology to publish before receiving permission from the authorized author(s) in writing. The published work is the copyright of the Journal of Thai-Nichi Institute of Technology.
References
J. M. Chang, C. C. Hsu, Y. L. Wang, and T. Y. Ho, “Finding the set of all hinge vertices for strongly chordal graphs in linear time,” Inf. Sci., vol. 99, no. 3-4, pp. 173–182, 1997.
H. Honma and S. Masuyama, “A parallel algorithm for finding all hinge vertices of an interval graph,” IEICE Trans. Inf. & Syst., vol. E84-D, no. 3, pp. 419–423, 2001.
H. Honma, Y. Nakajima, Y. Igarashi, and S. Masuyama, “Algorithm for finding maximum detour hinge vertices of interval graphs,” IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E97-A, no. 6, pp. 1365–1369, 2014.
M. Pal, “Intersection graphs: An introduction,” Annals Pure Appl. Math. (APAM), vol. 4, no. 1, pp. 43–91, 2013.
R. M. McConnell, “Linear-time recognition of circular-arc graphs,” Algorithmica, vol. 37, pp. 93–147, 2003.
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. New York, NY, USA: Academic Press, 1980.
T. Y. Ho, Y. L. Wang, and M. T. Juan, “A linear time algorithm for finding all hinge vertices of a permutation graph,” Inf. Process. Lett., vol. 59, no. 2, pp. 103–107, 1996.
H. Honma, K. Abe, and S. Masuyama, “Erratum and addendum to a linear time algorithm for finding all hinge vertices of a permutation graph,” Inf. Process. Lett., vol. 111, no. 18, pp. 891–894, 2011.
F. R. Hsu, M. K. Shan, H. S. Chao, and R. C. Lee, “Some optimal parallel algorithms on interval and circular-arc graphs,” J. Inf. Sci. Eng., vol. 21, pp. 627–642, 2005.
H. Honma and S. Masuyama, “An optimal parallel algorithm for finding all hinge vertices of a circular-arc graph,” IEICE Trans. Fundam. Electron. Commun. Comput., vol. E91.A, no. 1, pp. 383–391, 2008.
D. Bera, M. Pal, and T. K. Pal, “An efficient algorithm for finding all hinge vertices on trapezoid graphs,” Theory Comput. Syst., vol. 36, no. 1, pp. 17–27, 2003.
H. Honma, Y. Nakajima, and S. Masuyama, “An algorithm for hinge vertex problem on circular trapezoid graphs,” J. Inf. Process., vol. 25, pp. 945–948, 2017.
H. Honma, Y. Nakajima, Y. Igarashi, and S. Masuyama, “Algorithm for identifying the maximum detour hinge vertices of a permutation graph,” IEICE Trans. Fundam. Electron. Commun. Comput., vol. E98-A, no. 6, pp. 1161–1167, 2015.
H. Honma, Y. Nakajima, and S. Masuyama, “An algorithm for the influential hinge vertex problem on interval graphs,” J. Inf. Process., vol. 28, pp. 1047–1051, 2020.