Linear algorithms for parity path and two path problems on circular-arc graphs

DOI10.1007/3-540-51542-9_24MaRDI QIDQ4028893zbMATH OpenFDO

Authors A. Srinivasa Rao, C. Pandu Rangan

Publication date 28 March 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-51542-9_24

zbMATH Keywords

arcschordless pathscircular-arc graphinterval graphlinear algorithmsparity path problemtwo path problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Review text

[For the entire collection see Zbl 0753.00021.] A graph \(G\) is called a circular-arc graph if it is the intersection graph of a family of circular arcs around a circle. Presented is a method for solving path problems in proper circular-arc graphs, that is, circular-arc graphs where no arc is properly contained in another arc. In particular, the method solves these problems for circular-arc graphs: (1) the parity path problem, or finding two chordless paths--an even path and an odd path--between two nonadjacent vertices in a connected graph; (2) the two path problem, or finding two vertex-disjoint paths between designated pairs among four distinct vertices. The key procedure is applying a reduction process to the given family AF of arcs to obtain a new family AF\('\) of arcs for which there is now a vacant interval in the circle. The latter is therefore an interval graph. The authors then cite existing linear algorithms for solving both types of problems on interval graphs.

Recommendations

• Efficient reduction for path problems on circular-arc graphs
• Paths in interval graphs and circular arc graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Induced disjoint paths in circular-arc graphs in linear time
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs

Cited in

(6)

• The domatic number problem
• A polynomial algorithm for the parity path problem on perfectly orientable graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• scientific article; zbMATH DE number 5711694 (Why is no real title available?)
• A linear algorithms for the two paths problem on permutation graphs
• Efficient reduction for path problems on circular-arc graphs

This page was built for publication: Linear algorithms for parity path and two path problems on circular-arc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4028893)