1
$\begingroup$

For a hypergraph, I want to know the computational complexity of this step in my algorithm what is the computational complexity of this kind of sorting

Sort the hyperedges in descending order based on the number of common vertices with other hyperedges

I implement this step by calculating the degree of each vertex (the number of hyperedges it belongs). Then, for each hyperedge, I count the number of vertices that have degree greater than one and order the hyperedges

So the time complexity is $O(M+|\mathcal{E}|K_c+ |\mathcal{E}|)$ is it correct assuming that we have M vertices

$\endgroup$
  • 1
    $\begingroup$ The complexity depends on how you implement this step. $\endgroup$ – Yuval Filmus Jun 7 at 6:03
  • $\begingroup$ I implement this step by calculating the degree of each vertex (the number of hyperedges it belongs). Then, for each hyperedge, I count the number of vertices that have degree greater than one and order the hyperedges. $\endgroup$ – Salwa Jun 7 at 8:39
  • $\begingroup$ You should update your question with the complete details. $\endgroup$ – Yuval Filmus Jun 7 at 9:23
  • $\begingroup$ @YuvalFilmus Formally speaking, the complexity is a property of the problem; the actual running time achieved depends on the algorithm used. $\endgroup$ – David Richerby Jun 7 at 11:19
  • $\begingroup$ @DavidRicherby so my answer is incorrect? any advice about how to figure out this kind of sorting $\endgroup$ – Salwa Jun 7 at 11:29

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.