3
$\begingroup$

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.

$\endgroup$

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.