21–30 of 44 posts
Knowledge graphs are so under-utilised for practical things despite the fact that there is significant amount of useful research out there. Their problem is that they are expensive. I hope further research in ML would help elevate their relevance significantly. I am particularly fond of using knowledge graphs and graph theory for security related work.
The previously best known algorithm for deciding if a given edge could be added to a planar n-node graph, while keeping it planar, took time O(sqrt(n)). The new algorithm needs time only O((log n)^3), an exponential speedup.
How? But, yeah, for large graphs it should be (somewhat) faster.
The previously best known algorithm for deciding if a given edge could be added to a planar n-node graph, while keeping it planar, took time O(sqrt(n)). The new algorithm needs time only O((log n)^3), an exponential speedup.
https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...
The previously best known algorithm for deciding if a given edge could be added to a planar n-node graph, while keeping it planar, took time O(sqrt(n)). The new algorithm needs time only O((log n)^3), an exponential speedup.
This really only takes effect for very large values of n. The crossover is around 3x10^7 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...
I like graph theory. You draw some shapes, you draw some lines. It's like the kind of things you can do with your crayons. I reckon kids could be introduced to it earlier in friendlier language.
Earlier quoted context omitted.
This really only takes effect for very large values of n. The crossover is around 3x10^7 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...
In fairness, that's not _that_ huge of a graph.
The previously best known algorithm for deciding if a given edge could be added to a planar n-node graph, while keeping it planar, took time O(sqrt(n)). The new algorithm needs time only O((log n)^3), an exponential speedup.
This really only takes effect for very large values of n. The crossover is around 3x10^7 https://www.wolframalpha.com/input/?i=graph+ln%28n%29%5E3+vs...
- C1 = C2 = 1 => cross-over is 2x10^7
- C1 = 1, C2 = 10 => cross-over is 2x10^10
- C1 = 10, C2 = 1 => cross-over is 1668.2!
Of course the constant terms matter, but sqrt(N) < log2(N)^3 up until billions of nodes. For 2*32 nodes sqrt(N) is 2^16 and log2(N)^3 is 2^15. We deal with graphs of that size in electronic design automation, and planar graphs don't need metal crossovers, but we aren't adding one connection at a time. So this result in itself isn't going to be terribly applicable, but may lead to further insights and development of i…
I work with the researchers, and I think they'll be interested in knowing which version of the problem practitioners like yourself are most interested in. Do you ever add/remove edges, perhaps in bulk? Or do are you mostly interested in finding "best possible" layouts for static datasets?
Earlier quoted context omitted.
n=nodes>0; n^0.5=(log n)^3, n~24128091.7 , which is millions not billions? https://www.wolframalpha.com/input/?i=sqrt%28n%29%3D%28log+n...
You're using natural log, for my quick-and-dirty I used log2, which gives a slightly higher crossover point. The exact crossover depends on the size of the constant term, of course.