Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949854 | Discrete Applied Mathematics | 2017 | 16 Pages |
Abstract
On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andreas Darmann, Ulrich Pferschy, Joachim Schauer,