# I found an algorithm for computing multiple MSTs in O(E/V). Is this publishable? [closed]

Let's say you use Kruskal's or Prim's algorithm to compute the first MST, and you want to check to see if there are other MSTs. I can do this in O(E/V) time.

The algorithm uses a priority queue (which can be constructed in O(N) ). Kruskal's and Prim's already use priority queues, but they're slower than the linear time algorithms listed below.

I know there are already algorithms that can find a single MST in linear time:

• A randomized algorithm can solve it in linear expected time. [Karger, Klein, and Tarjan, "A randomized linear-time algorithm to find minimum spanning trees", J. ACM, vol. 42, 1995, pp. 321-328.]
• It can be solved in linear worst case time if the weights are small integers. [Fredman and Willard, "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719--725.]
• Otherwise, the best solution is very close to linear but not exactly linear. The exact bound is O(m log beta(m,n)) where the beta function has a complicated definition: the smallest i such that log(log(log(...log(n)...))) is less than m/n, where the logs are nested i times. [Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109--122.]

I'm not sure if these algorithms use priority queues. It doesn't really matter since I could just use one of these algorithms to find the first MST in O(N) then construct a priority queue in O(N) then find all the other MSTs in O(E/V). Overall, this would take O(N).

I just came up with this algorithm for a class assignment. The algorithm my TA used to find multiple MSTs took O(N^2) or O(N^3), and so he said I should try to see if this is publishable.

Edit: I realized my algorithm only finds some of the MSTs in O(E/V). To be more specific: on all graphs, it finds some additional MSTs within time O(E/V), and I'm not sure how to find all possible MSTs.

The input to the algorithm is: 1. an MST (a list of Edge objects. Edge.weight, Edge.vertex1 and Edge.vertex2 are fields of the object). 2. A graph (a list of Edges and Verteces).

The output (for all graphs) is some (but not all) of its MSTs.

## closed as off-topic by KavehDec 22 '13 at 17:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

• What is your exact claim? That, if you're given a graph $G=(V,E)$ and a spanning tree $T$, you can determine in time $O(|E|/|V|)$ whether there is another spanning tree? If so, that can't be correct. If $G$ has constant degree, your algorithm would have to run in constant time, which doesn't even give you enough time to discover that $G$ has constant degree. – David Richerby Dec 20 '13 at 7:31
• I think the OP's claim is that after computing the MST, one can use the internal priority queue of the MST algorithm to determine whether the MST is unique in $O(m/n)$ additional time. But not every MST algorithm uses a priority queue; see Boruvka's algorithm, or the traditional sort+scan formulation of Kruskal's algorithm. – Jeffε Dec 20 '13 at 13:48
• How about some encouragement for enterprising students rather than downvotes? – Yuval Filmus Dec 20 '13 at 14:55
• Does your algorithm find MSTs or just count them? You certainly can't find them all in polynomial time in general because a complete graph on $n$ vertices with unit edge weights has $n^{n-2}$ MSTs, by Cayley's formula. If anyone's going to be able to evaluate the importance of your discovery (it's not my direct area of expertise), you need to give a precise statement of what you've achieved. What exactly is the input to your algorithm? What is its output? What time complexity are you claiming for it? – David Richerby Dec 20 '13 at 23:59
• @Yuval, the post is unclear, and it is not clear if the TA thinks the algorithm is correct or not (i.e. one of incorrect heuristics that students come up with all the time in undergraduate courses where they cannot prove it to be correct but the TA cannot come up with a counter-example). I think this is off-topic if this was an assignment in an undergraduate course and TA/Instructor has not verified the solution. – Kaveh Dec 21 '13 at 0:03