An Algorithm for the All-pair Shortest Path Problem on Circular Trapezoid Graphs

Main Article Content

Hirotoshi Honma
Yoko Nakajima
Tsendsuren Urangoo
Yuto Tamori

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.

Downloads

Download data is not yet available.

Article Details

Section
Research Article
Author Biography

Hirotoshi Honma, Department of Creative Engineering, National Institute of Technology, Kushiro College, Japan

 

 

References

[1] E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerische Mathematlk, vol. 1, pp. 269–271, 1959.

[2] 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.

[3] R. W. Floyd, “Algorithm 97: Shortest path,” Communications of the ACM, vol. 5, no. 6, pp. 344-348, Jun. 1962.

[4] S. Warshall, “A theorem on boolean matrices,” J. ACM, vol. 9, no.1, pp. 11–12, Jan. 1962.

[5] 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.

[6] 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.

[7] M. Debski, K. J. Szaniawski and Z. Lonc, “Bundling all shortest paths,” Discrete Applied Mathematics, vol. 277, pp. 82–91, Apr. 2020.

[8] 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.

[9] 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.

[10] 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.

[11] 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.

[12] 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.

[13] W. L. Lin, “Circular and circle trapezoid graphs,” J. Sci. Eng. Tech., vol. 2, no. 2, pp. 11–17, 2006.

[14] 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.

[15] 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.

[16] 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.

[17] R. D. Lou and M. Sarrafzadeh, “Circular permutation graph family with applications,” Discrete Applied Mathematics, vol. 40, no. 3, pp. 433–457, Dec. 1992.

[18] 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.

[19] 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.

[20] 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.

[21] 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.