k-best enumeration

2014/12/16 by David Eppstein, Eppstein, David · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1412.5075

openalex publication_date 2014/12/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We survey k-best enumeration problems and the algorithms for solving them, including in particular the problems of finding the k shortest paths, k smallest spanning trees, and k best matchings in weighted graphs.

Citations

• A note on two problems in connexion with graphs
• Two-level, Many-Paths Generation

Cited by

• Disjoint Tours and the Price of Diversity

Related

• Twenty Open Problems in Enumeration of Matchings
• Enumeration of maximum matchings of graphs
• An Approximation Algorithm for K-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
• Enumeration of Enumeration Algorithms
• Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study