A Sequential Algorithm to Solve Next-to-Shortest Path Problem on Circular-arc Graphs

Abstract

In this article, we study the problem of finding the next-to-shortest path in circular-arc graph. A next-to-shortest path between any pair of vertices in a shortest path amongst all paths between those vertices with length strictly greater than the length of the shortest path. The next-to-shortest path problem in a directed graph in NP-hard. Here we deigned a polynomial time algorithm to solve this problem for the circular-arc graph.