simonson@uicbert.eecs.uic.edu (05/29/90)
In Shannon's Swithching game, two players alternately choose edges of a given undirected graph until all the edges are chosen. There are two distinguished vertices in the graph, u and v. The goal of one player is to connect these two vertices and the goal of the other player is to separate them. It is known that the "connecting" player can always win if there are two edge disjoint spanning trees of the graph. Does anyone know an algorithm for determining whether a given undirected graph has two edge disjoint spanning trees? If this result is well known, is it a special case of a larger theory? and If such an algorithm exists, and one determines that a given graph has two edge disjoint spanning trees, then is it easy to find them?
dgc@MATH.UCLA.EDU ("David G. Cantor") (06/02/90)
simonson@uicbert.eecs.uic.edu In article <88200006@uicbert.eecs.uic.edu>
simonson@uicbert.eecs.uic.edu writes:
In Shannon's Swithching game, two players alternately choose
edges of a given undirected graph until all the edges are
chosen. There are two distinguished vertices in the graph, u
and v. The goal of one player is to connect these two vertices
and the goal of the other player is to separate them. It is
known that the "connecting" player can always win if there are
two edge disjoint spanning trees of the graph.
Does anyone know an algorithm for determining whether a given
undirected graph has two edge disjoint spanning trees? If this
result is well known, is it a special case of a larger theory?
and if such an algorithm exists, and one determines that a given
graph has two edge disjoint spanning trees, then is it easy to
find them?
------------------------------------------------------------------------
The answer to all of the questions is YES.
This is a result in matroid theory.
Some references are:
1. Alfred Lehman, "An Introduction to Matroid Theory", SIAM
J. 12 (1964), pp 687-725.
2. John Bruno and Louis Weinberg, "A Constructive Graph-Theoretic
Solution of the Shannon Switching Game", J. IEEE Trans. Circuit
Th. CT-17 (1970), pp 74-80.
3. W. J. Tutte, "Lectures on Matroids", J. of Research of the National
Bureau of Standards 69B (1973), pp 1-77.
Lehman was the original "solver" of this game. Unfortunately, none of
the above references is comprehensible. The standard texts on Matroid
Theory generally don't give the solution but refer the reader to one of
these three texts.
dgc
David G. Cantor
Department of Mathematics
University of California at Los Angeles
Internet: dgc@math.ucla.edukhuller@svax.cs.cornell.edu (Samir Khuller) (06/04/90)
> Article 1849 of comp.theory: > >From: simonson@uicbert.eecs.uic.edu > Subject: Shannon's Switching Game > Date: 29 May 90 01:47:00 GMT > > In Shannon's Swithching game, two players alternately choose edges > of a given undirected graph until all the edges are chosen. > There are two distinguished vertices in the graph, u and v. The goal of > one player is to connect these two vertices and the goal of the other > player is to separate them. It is known that the "connecting" player > can always win if there are two edge disjoint spanning trees of the > graph. > > Does anyone know an algorithm for determining whether a given undirected > graph has two edge disjoint spanning trees? If this result is well known, > is it a special case of a larger theory? and If such an algorithm exists, > and one determines that a given graph has two edge disjoint spanning trees, > then is it easy to find them? > The best algorithm for this problem is due to Gabow and Westermann (see STOC proceedings 1988). However, one may find the algorithm hard to follow without much background in matroid theory. The reference that I recommend is a paper by Tarjan and ?(a name that i don't recall), the paper appeared in Math of OR a few years ago (a reference can be found in Gabow's paper that was in STOC 88). I don't have any of them nearby so i cannot check -- sorry. Hope that helps. samir khuller