Title: Strategies for the Shannon switching game
Archive date: Mon Nov 21 12:18:21 1994
Abstract: We give a simple prove that Short has a winning strategy for the Shannon switching game iff there are two edge disjoint trees with the same set of vertices connecting the two distinguished vertices. This theorem was first proved by Lehman in 1964 but his proof used matroid theory and appeared hard. As a result of our analysis, we will also give a strategy for Cut in the case where Short cannot force a win.
Available formats: This paper was prepared with AMS-LaTeX . It is available as TeX source or in dvi format.