Alternating Reachability
From MaRDI portal
Publication:6476372
arXivmath/0511675MaRDI QIDQ6476372FDOQ6476372
Authors: Amitava Bhattacharya, Uri N. Peled, Murali K. Srinivasan 
Publication date: 28 November 2005
Abstract: We consider a graph with colored edges. A trail (vertices may repeat but not edges) is called emph{alternating} when successive edges have different colors. Given a set of vertices called emph{terminals}, the emph{alternating reachability} problem is to find an alternating trail connecting distinct terminals, if one exists. A special case with two colors is searching for an augmenting path with respect to a given matching. In another special case with two colors red and blue, the emph{alternating cone} is defined as the set of assignments of nonnegative weights to the edges such that at each vertex, the total red weight equals the total blue weight; in a companion paper we showed how the search for an integral weight vector within a given box in the alternating cone can be reduced to the alternating reachability problem in a 2-colored graph. We define an obstacle, called a emph{Tutte set}, to the existence of an alternating trail connecting distinct terminals in a colored graph, and give a polynomial-time algorithm, generalizing the blossom algorithm of Edmonds, that finds either an alternating trail connecting distinct terminals or a Tutte set. We use Tutte sets to show that an an edge-colored bridgeless graph where each vertex has incident edges of at least two different colors has a closed alternating trail. A special case with two colors one of which forms a matching yields a combinatorial result of Giles and Seymour. We show that in a 2-colored graph, the cone generated by the characteristic vectors of closed alternating trails is the intersection of the alternating cone with the cone generated by the characteristic vectors of cycles in the underlying graph.
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
This page was built for publication: Alternating Reachability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6476372)
