The parity path problem on some subclasses of perfect graphs (Q1923620): Difference between revisions

The parity path problem is the problem of finding two paths of different parity between two vertices. The problem is NP-complete on general graphs. In this paper, the authors consider the problem for comparability (i.e., transitively orientable), permutation, and cocomparability graphs. They give polynomial algorithms for these graphs by using the transitive orientability of the graphs to modify a breadth-first search.