Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Hmm? Trees are just acyclic and connected graphs in graph theory. Why wouldn't you use the same tools that apply to graphs in general?


Acyclicity usually makes it possible to come up with a specialized algorithm that works better on trees than an algorithm that needs to handle all possible graphs. For example, many NP-complete problems become fixed-parameter tractable if you fix the tree-width of the graph (essentially, how many nodes you have to bag together until the graph looks like a tree).

Because of this, algorithms on trees are often very different from general graph algorithms in practice. You could use the same tools, but it would be unnecessarily slow and/or complex.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: