0
$\begingroup$

I am using Pawel Winter's algorithm to enumerate all spanning trees. What I need to do now is enumerate all spanning trees where one edge say e1 remains in the tree and the edge e2 is in e1's fundamental cutset. I'm not sure where to start so any information is appreciated.

Edit: is there a graph operation that can be performed to guarantee the edge e2 is in e1's cutset? …Kind of like how contracting edges helps find all spanning trees with that edge in it.

Improve this question
$\endgroup$
2
  • $\begingroup$ At least listing spanning trees where $e_1$ is in the tree is easy: contract it, and find spanning trees of the contracted graph. Maybe something similar (deletion?) can be done for $e_2$. $\endgroup$
    – Sam Hopkins
    Commented Aug 23 at 1:45
  • $\begingroup$ That's a good suggestion, I have tried contracting along e1 and removing e2. But I still get some spanning trees where e2 is not in e1's cutset. $\endgroup$
    – dubc
    Commented Aug 23 at 1:49

1 Answer 1

Reset to default
0
$\begingroup$

Contract $e_1$ and delete $e_2$. Say $G$ is the original graph and $H$ is the new graph. Now run the tree enumeration algorithm on $H$. After reversing the contraction, you get all the spanning trees of $G$ that include $e_1$ and avoid $e_2$. Some of these are not what you need, but a large fraction of them will be (I'm guessing about half in typical cases). Select the trees you need by checking if the path in the tree between the two ends of $e_2$ contains $e_1$.

Note that there is a small detail to watch. When you contract $e_1$ you need to keep track of multiple edges as they are different after when you reverse the contraction. If the tree enumerator only handles simple graphs, this means that each spanning tree in $H$ may become several spanning trees in $G$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I like this too; my only concern was having to traverse the path from e1 to e2 for each possible tree. It could be a small path or a big path so I was worried that what I save from contracting e1 and removing e2 I lose from checking the path of each tree in H. $\endgroup$
    – dubc
    Commented Aug 23 at 1:54
  • $\begingroup$ If $G$ is dense then most spanning trees will not contain $e_1$, so a lot is lost if the contraction is not done. Also, I don't know the algorithm but the tree generation probably makes trees in an order where most trees are only slightly different from the one before and you may be able to use this property to speed the check. For a start, I'd test if the tree path between the ends of $e_2$ is preserved for a large fraction of transitions. $\endgroup$
    – Brendan McKay
    Commented Aug 23 at 2:59
  • $\begingroup$ Thanks! I do think this is the best solution so far. I think you're correct about Winters Algorithm too, so skipping over those invalid trees might help reduce the total number of operations. $\endgroup$
    – dubc
    Commented Aug 23 at 3:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .