2012 | OriginalPaper | Buchkapitel
Alternating Reachability and Integer Sum of Closed Alternating Trails
The 3rd Annual Uri N. Peled Memorial Lecture
verfasst von : Amitava Bhattacharya
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider a graph with colored edges and study the following two problems.
(i) Suppose first that the number of colors is two, say red and blue. A nonnegative real vector on the edges is said to be
balanced
if the red sum equals the blue sum at every vertex. A
balanced subgraph
is a subgraph whose characteristic vector is balanced (i.e., red degree equals blue degree at every vertex). By a
sum
(respectively,
fractional sum
) of cycles we mean a nonnegative integral (respectively, nonnegative rational) combination of characteristic vectors of cycles. Similarly, we define sum and fractional sum of balanced subgraphs. We show that a balanced sum of cycles is a fractional sum of balanced subgraphs.
(ii) Next we consider the problem of finding a necessary and sufficient condition for the existence of a balanced subgraph containing a given edge. This problem is easily reduced to the alternating reachability problem, defined as follows. Given an edge colored graph (here we allow ≥ 2 colors) a trail (vertices may repeat but not edges) is called
alternating
when successive edges have different colors. Given a set of vertices called
terminals
, the
alternating reachability
problem is to find an alternating trail connecting distinct terminals, if one exists. By reduction to the classical case of searching for an augmenting path with respect to a matching we show that either there exists an alternating trail connecting distinct terminals or there exists an obstacle, called a
Tutte set
, to the existence of such trails. We also give a Gallai-Edmonds decomposition of the set of nonterminals.
This work started when Uri Peled and Murali Srinivasan met in Caesarea Edmond Benjamin de Rothschild Foundation Institute for Interdisciplinary Applications of Computer Science at the University of Haifa, Israel during May–June 2003. This led to many interesting questions and some of them are still open. In this talk we would like to discuss some of them.