I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, and finding a reference is the best solution.

We have a connected hypergraph. We want to choose a list of hyperedges satisfying the following property: if you add the hyperedges to the empty hypergraph one by one, in each step the number of connected components reduces. At the beginning we have $n$ components, and at the end of these steps we have a single component. Suppose that in the $i$-th step, the number of components reduces by $a_i$. If we have $t+1$ steps, we want to minimize $\max(a_1,a_2,\dots,a_t)$.

I have an algorithm in which the complexity of each step is $O(n^{a_i})$. I would be glad to find a reference for this problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.