News for hackers. Stuff that matters.
Re:I don’t understand Graph Theory by yorwba on Thursday February 22, 2018 @08:56AM (#16437529)
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.

There are no comments on this comment yet.