An Algorithm for the All-pair Shortest Path Problem on Circular Trapezoid Graphs
Article Sidebar
Main Article Content
Abstract
The shortest path problem involves finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. This is a fundamental and important problem in graph theory, and it has been applied for solving numerous problems such as the minimum connected dominating set, minimum-weight circle-cover, and minimum cardinality Steiner set problems. The single-source shortest path problem involves finding the shortest paths between a given vertex and all other vertices. The all-pair shortest path problem involves the determination of the shortest graph distances between every pair of vertices in a given graph. In general, it is known that efficient sequential or parallel algorithms can be developed by restricting the classes of graphs. Numerous studies have been conducted on the shortest path problems on several intersection graphs. A circular trapezoid graph is a proper superclass of trapezoid graphs and circular-arc graphs. In this study, we present an O(n2) time algorithm to solve the all-pair shortest path problem on circular trapezoid graphs.
Article Details
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
E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematlk, vol. 1, pp. 269–271, 1959.
M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” J. ACM, vol. 34, no. 3, pp. 596–615, Jul. 1987.
R. W. Floyd, “Algorithm 97: Shortest path,” Communications of the ACM, vol. 5, no. 6, pp. 344-348, Jun. 1962.
S. Warshall, “A theorem on boolean matrices,” J. ACM, vol. 9, no.1, pp. 11–12, Jan. 1962.
Y. Kobayashi and R. Sako, “Two disjoint shortest paths problem with non-negative edge length,” Operations Research Letters, vol. 47, no. 1, pp. 66–69, Jan. 2019.
C. Glacet, N. Hanusse, D. Ilcinkas, and C. Johnen, “Disconnected components detection and rooted shortest-path tree maintenance in networks,” J. Parallel and Distributed Computing, vol. 132, pp. 299–309, Oct. 2019.
M. Debski, K. J. Szaniawski and Z. Lonc, “Bundling all shortest paths,” Discrete Applied Mathematics, vol. 277, pp. 82–91, Apr. 2020.
L. Di Puglia Pugliese, D. Ferone, P. Festa, and F. Guerriero, “Shortest path tour problem with time windows,” European Journal of Operational Research, vol. 282, no. 1, pp. 334–344, Apr. 2020.
F. R. Hsu, 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, no. 3, pp. 627–642, May 2005.
O. H. Ibarra and Q. Zheng, “An optimal shortest path parallel algorithm for permutation graphs,” J. Parallel and Distributed Computing, vol. 24, no. 1, pp. 94–99, Jan. 1995.
S. Mondal, M. Pal, and T. K. Pal, “An optimal algorithm for solving all-pairs shortest paths on trapezoid graphs,” Int. J. Computational Engineering Science, vol. 3, no. 2, pp. 103–116, 2002.
S. C. Barman, S. Mondal, and M. Pal, “An efficient algorithm to find next-to-shortest path on trapezoid graphs,” Advances in Applied Mathematical Analysis, vol. 2, no. 2, pp. 97–107, 2007.
W. L. Lin, “Circular and circle trapezoid graphs,” J. Sci. Eng. Tech., vol. 2, no. 2, pp. 11–17, 2006.
H. Honma, Y. Nakajima, Y. Aoshima, and S. Masuyama, “A lineartime algorithm for constructing a spanning tree on circular trapezoid graphs,” IEICE Trans. Fundamentals, vol. E96-A, no. 6, pp. 1051–1058, Jun. 2013.
D. Chen, D. T. Lee, R. Sridhar, and C. Sekharam, “Solving the all-pair shortest path query on interval and circular-arc graphs,” Networks, vol. 31, no. 4, pp. 249–258, 1998.
T. W. Kao and S. J. Horng, “Optimal algorithms for computing articulation points and some related problems on a circular-arc graph,” Parallel Computing, vol. 21, no. 6, pp. 953–969, Jun. 1995.
R. D. Lou and M. Sarrafzadeh, “Circular permutation graph family with applications,” Discrete Applied Mathematics, vol. 40, no. 3, pp. 433–457, Dec. 1992.
H. Honma, S. Honma, and S. Masuyama, “An optimal parallel algorithm for constructing a spanning tree on circular permutation graphs,” IEICE Transactions on Information and Systems, vol. E92-D, no. 2, pp. 141–148, Feb. 2009.
H. Honma, K. Abe, Y. Nakajima, and S. Masuyama, “Linear time algorithms for finding articulation and hinge vertices of circular permutation graphs,” IEICE Trans. Inf. & Syst., vol. E96-D, no. 3, pp. 419–425, Mar. 2013.
H. Honma, Y. Nakajima, and S. Masuyama, “An algorithm for hinge vertex problem on circular trapezoid graphs,” Journal of Information Processing, vol. 25, pp. 945–948, Dec. 2017.
D. Bera, M. Pal, and T. K. Pal, “An efficient algorithm for finding all hinge vertices on trapezoid graphs,” Theory of Computing Systems, vol. 36, no. 1, pp. 17–27, Feb. 2003.