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$
7
  • 1
    $\begingroup$ The complexity depends on how you implement this step. $\endgroup$ Jun 7 '19 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 '19 at 8:39
  • $\begingroup$ You should update your question with the complete details. $\endgroup$ Jun 7 '19 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$ Jun 7 '19 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 '19 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.