On Mon, Apr 19, 2004 at 11:43:19AM -0400, Michael Kleber wrote:
Ah, quite right. Along similar lines, I came up with the following for the two-edge cut sets. Build a spanning tree and a matrix which lets you easily walk between any pair of vertices along the tree, just as you say. Each edge in the tree is assigned a list, initially empty, of its "cut partners". Then for each edge e not in the tree, walk along the tree between e's two endpoints and add e to the list of "cut parnters" of each edge you use. At the end, any edge in the tree whose cut-partner list is of length 0 is a cut edge, and any whose list is of length 1 is half of a two-edge cut set, with the list's sole element being the other edge you need to cut.
I don't think that's correct in all cases. In particular, you sometimes miss two-edge cut sets. Consider a graph that's just a big loop, for instance. Cutting any two edges disconnects the graph (total of (n choose 2) pairs), but you only find n-1 pairs. Worse, you sometimes fail to find two-edge cut sets altogether: consider the graph with n vertices with one edge from k to k+1 and two edges from 1 to n, with the spanning tree consisting of all the edges from k to k+1. Then each edge in the spanning tree ends up with two cut partners, although there are plenty of two-edge cut sets. Peace, Dylan