Efficient reduction for path problems on circular-arc graphs

An efficient reduction process for path problems on circular-arc graphs is introduced. For the parity path problem, this reduction gives an O(n+m) algorithm for proper circular-arc graphs, and an O(n+m) algorithm for general circular-arc graphs. This reduction also gives an O(n+m) algorithm for the two path problem on circular-arc graphs. © 1991 BIT Foundations.