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

2016/09/23 by Miguel Raggi, Raggi, Miguel
Computer Science · #Advanced Database Systems and Queries #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.1609.07450

openalex publication_date 2016/09/23 · arxiv created 2018/02/21 · arxiv updated 2018/02/22 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

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

Related

• Speeding up shortest path algorithms
• A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph
• On Computing Top-k Simple Shortest Paths from a Single Source
• Finding Optimal Longest Paths by Dynamic Programming in Parallel
• Finding k Simple Shortest Paths and Cycles