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

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.