maxdan94
  • Member for 8 years, 1 month
  • Last seen more than a month ago
  • Paris, France
Count $k$-hop neighborhood for every vertex
2 votes

There is this quasi-linear time approximation algorithm based on HyperLogLog: https://papers-gamma.link/paper/187

View answer
Bipartite graph projections, with threshold
1 votes

My two cents: The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$. Maybe you are not looking for a worst case ...

View answer
Is this vertex ordering optimization NP-Hard?
1 votes

The proof here also shows NP-hardness of the problem. It shows NP-hardness of the less constrained problem where we look for an orientation of the edges instead of an ordering of the nodes (that is ...

View answer
Algorithms for finding all cliques of a given degree in a graph
1 votes

This maybe: https://papers-gamma.link/paper/32 With an open source implementation here: https://github.com/maxdan94/kClist

View answer
Simplifying a parametrized complexity given that a parameter is in $o(n)$
1 votes

Thanks a lot for your comment, I think it can be an answer. I have this practical algorithm and I'm trying to express its running time as a function of some parameters and not only the size of the ...

View answer
Data for testing graph algorithms
0 votes

Links to real-world graphs with more than 1G edges: https://sites.google.com/view/limass/datasets A collection of smaller real-world graphs: http://snap.stanford.edu/data/index.html

View answer
Simplifying a parametrized complexity given that a parameter is in $o(n)$
Accepted answer
0 votes

I've discussed with an ``FPT and XP guy'', we found that I shouldn't have written the problem in such a way. Let me rewrite it. This is related to graph algorithms. Chiba and Nishizeki showed that it ...

View answer
find the densest subgraph of size k
-1 votes

This is me again, more than 3 years after asking this question. Here is a code that can solve the weighted version of the problem in some real-world weighted graphs efficiently: https://github.com/...

View answer