Skip to main content
Top

2012 | OriginalPaper | Chapter

Alternating Reachability and Integer Sum of Closed Alternating Trails

The 3rd Annual Uri N. Peled Memorial Lecture

Author : Amitava Bhattacharya

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer Berlin Heidelberg

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadata
Title
Alternating Reachability and Integer Sum of Closed Alternating Trails
Author
Amitava Bhattacharya
Copyright Year
2012
Publisher
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-34611-8_3

Premium Partner