Content Tags

There are no tags.

Finding long simple paths in a weighted digraph using pseudo-topological orderings.

RSS Source
Authors
Miguel Raggi

Given a weighted digraph D, finding the longest simple path is well known tobe NP-hard. Furthermore, even giving an approximation algorithm is known to beNP-hard. In this paper we describe an efficient heuristic algorithm for findinglong simple paths, using an hybrid approach of DFS and pseudo-topologicalorders, a a generalization of topological orders to non acyclic graphs, via aprocess we call "opening edges". An implementation of this algorithm won theOracle MDC 2015 coding competition.

Stay in the loop.

Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.