Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width.
Lars JaffkeO-joung KwonJan Arne TellePublished in: CoRR (2017)
Keyphrases
- polynomial time complexity
- optimization problems
- disjoint paths
- learning algorithm
- computational complexity
- benchmark problems
- special case
- graph theory
- fixed parameter tractable
- data structure
- run times
- partial solutions
- approximation algorithms
- np complete
- combinatorial optimization
- random graphs
- computationally hard
- bounded treewidth
- decision problems
- graph isomorphism
- np hard
- evolutionary algorithm
- graph layout