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

Question

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 that my algorithm will only find some of the other MSTs in O(E/V) time. I say it finds the other MSTs in O(E/V) time because that's how long it takes to iterate over all the edges from a particular vertex (on average).

EDIT: There was a flaw in my proof. Sorry for getting excited about this.

Answer 1

Sure, this would be a good result provided it is correct. As a simple sanity check try running it on a complete graph (there is an edge connecting every pair of nodes) with all edge weights set to 1. In such a graph with n nodes, there are n minimum spanning trees. Although premature, I have doubts that your algorithm can find all n trees in O(n) time. But good luck!

Answer 2

No, it's not publishable. There are linear-time algorithms known for the tree-path-maxima problem (see the citation below), which, given one minimum spanning tree, can be used to determine in linear time which of the other edges in the graph belong to at least one minimum spanning tree (= the edges that have weight equal to the path maximum between their endpoints). Every spanning tree in the edge subgraph obtained by omitting those edges belonging to no minimum spanning tree is a minimum spanning tree.

@incollection{
year={2010},
isbn={978-3-642-11408-3},
booktitle={Graph-Theoretic Concepts in Computer Science},
volume={5911},
series={Lecture Notes in Computer Science},
editor={Paul, Christophe and Habib, Michel},
doi={10.1007/978-3-642-11409-0_16},
title={An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees},
url={http://dx.doi.org/10.1007/978-3-642-11409-0_16},
publisher={Springer Berlin Heidelberg},
author={Hagerup, Torben},
pages={178-189}
}