3 ms·
Ask HN: Are new graph algorithms still being devised?
Just wondering if there are graph algorithms beyond the textbook ones that are still being designed/devised? This post [1] from a few days back prompted this question.
[1] https://news.ycombinator.com/item?id=27294401
- duped 5y agoAll the time! Often you'll need to come up with a modification or variant of a textbook algorithm for particular applications. For example, node-based editors in game engines and other media software need a few key algorithms, but the ordering of incoming/outgoing edges have meaningful semantics that might need to be considered. You may need to use a custom algorithm to write a solver for a particular problem, for example latency/delay compensation in various networks (audio, distributed sensors, etc). Other times you may want to combine multiple algorithms into single traversals, which is often used in single-pass compilers or parsers. These can be tricky if the traversal modifies the graph. Then there are hypergraphs, which are so generic you probably need to treat your application as a special case.
- jaxk 5y agoYeah I get that you have to tweak canonical algorithms to suit the current problem but I am thinking more about developing algo for open problems or improving the performance at research level. Also, are algorithms beyond basic ones like shortest path, a* search and network flow are ever needed in real world situations? They all seem done and dusted pretty much.
- duped 5y agoYes graph algorithms are actively researched. You can browse arxiv.org and see plenty of recent submissions: https://arxiv.org/search/?query=Graph&source=header&searchtype=all https://arxiv.org/search/?query=Graph&source=header&searchty... For applications, compilers need graph coloring. Task schedulers need graph cuts. Since these are NP complete there is plenty of room for research on specific implementations with various heuristics.
- yun111 5y agoI wrote a paper detailing one last month, and conjectured that a different approach would work as well. I believe that other researchers are close to proving my conjecture. So yes.
- high_byte 5y agoadding to what others said: graph based neural networks is a hot topic and I believe is the next major breakthroughs in AI.