Path: utzoo!attcan!uunet!tut.cis.ohio-state.edu!snorkelwacker!mit-eddie!uw-beaver!cornell!khuller
From: khuller@svax.cs.cornell.edu (Samir Khuller)
Newsgroups: comp.theory
Subject: shannon's switching game
Message-ID: <41702@cornell.UUCP>
Date: 4 Jun 90 16:36:21 GMT
Sender: nobody@cornell.UUCP
Reply-To: khuller@cs.cornell.edu (Samir Khuller)
Distribution: comp
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 29

> 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