Title: An Optimal Algorithm for Shortest Paths on Weighted Interval and Circular-Arc Graphs, with Applications Mikhail J. Atallah Department of Computer Sciences Purdue University West Lafayette, IN 47907 e-mail: mja@cs.purdue.edu Danny Z. Chen Department of Computer Science and Engineering University of Notre Dame Notre Dame, IN 46556 e-mail: chen@cse.nd.edu and D. T. Lee* Department of Electrical and Computer Engineering Northwestern University Evanston, IL 60208 e-mail: dtlee@ece.nwu.edu * Supported in part by the Leonardo Fibonacci Institute in Trento, Italy, by the National Science Foundation, and the Office of Naval Research under the under the Grants CCR-8901815, CCR-9309743 and N00014-93-1-0272. Abstract We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcs and the sorted list of the interval endpoints. Our algorithm solves this problem optimally in O(n) time, where n is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is an O(qn + n\log n) time algorithm for the minimum-weight circle-cover problem, where q is the minimum number of arcs crossing any point on the circle; the n\log n term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were O(n\log n) for this shortest paths problem, and O(qn \log n) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar \log n-factor improvements in other problems on such graphs. Key Words: Shortest paths, interval graphs, circular-arc graphs, union-find algorithms, minimum circle cover. Algorithmica, 14,5, Nov. 1995, 429-441.