Years and Authors of Summarized Original Work
-
1959; Hoffman, Pavley
-
1963; Clarke, Krikorian, Rausen
-
1968; Murty
-
1971; Yen
-
1972; Lawler
-
1977; Gabow
-
1982; Katoh, Ibaraki, Mine
-
1985; Hamacher, Queyranne
-
1987; Chegireddy, Hamacher
-
1993; Frederickson
-
1997; Eppstein, Galil, Italiano, Nissenzweig
-
1998; Eppstein
-
2007; Hershberger, Maxel, Suri
-
2013; Chen, Kanj, Meng, Xia, Zhang
Problem Definition
K-best enumeration problems are a type of combinatorial enumeration in which, rather than seeking a single best solution, the goal is to find a set of k solutions (for a given parameter value k) that are better than all other possible solutions. Many of these problems involve finding structures in a graph that can be represented by subsets of the graph’s edges. In particular, the k shortest paths between two vertices s and t in a weighted network are a set of k distinct paths that are shorter than all other paths, and other problems such as the k smallest spanning trees of a graph or the k...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
This material is based upon work supported by the National Science Foundation under Grant CCF-1228639 and by the Office of Naval Research under Grant No. N00014-08-1-1015.
Recommended Reading
Chegireddy CR, Hamacher HW (1987) Algorithms for finding K-best perfect matchings. Discret Appl Math 18(2):155–165. doi:10.1016/0166-218X(87)90017-5
Chen J, Kanj IA, Meng J, Xia G, Zhang F (2013) Parameterized top-K algorithms. Theor Comput Sci 470:105–119. doi:10.1016/j.tcs.2012.10.052
Clarke S, Krikorian A, Rausen J (1963) Computing the N best loopless paths in a network. J SIAM 11:1096–1102
Eppstein D (1998) Finding the k shortest paths. SIAM J Comput 28(2):652–673. doi:10.1137/S0097539795290477
Eppstein D, Galil Z, Italiano GF, Nissenzweig A (1997) Sparsification–a technique for speeding up dynamic graph algorithms. J ACM 44(5):669–696. doi:10.1145/265910.265914
Frederickson GN (1993) An optimal algorithm for selection in a min-heap. Inf Comput 104(2):197–214. doi:10.1006/inco.1993.1030
Gabow HN (1977) Two algorithms for generating weighted spanning trees in order. SIAM J Comput 6(1):139–150. doi:10.1137/0206011
Hamacher HW, Queyranne M (1985) K best solutions to combinatorial optimization problems. Ann Oper Res 4(1–4):123–143. doi:10.1007/BF02022039
Hershberger J, Maxel M, Suri S (2007) Finding the k shortest simple paths: a new algorithm and its implementation. ACM Trans Algorithms 3(4):A45. doi:10.1145/1290672.1290682
Hoffman W, Pavley R (1959) A method for the solution of the Nth best path problem. J ACM 6(4):506–514. doi:10.1145/320998.321004
Katoh N, Ibaraki T, Mine H (1982) An efficient algorithm for K shortest simple paths. Networks 12(4):411–427. doi:10.1002/net.3230120406
Lawler EL (1972) A procedure for computing the K best solutions to discrete optimization problems and its application to the shortest path problem. Manag Sci 18:401–405. doi:10.1287/mnsc.18.7.401
Murty KG (1968) Letter to the editor–an algorithm for ranking all the assignments in order of increasing cost. Oper Res 16(3):682–687. doi:10.1287/opre.16.3.682
Yen JY (1971) Finding the K shortest loopless paths in a network. Manag Sci 17:712–716. http://www.jstor.org/stable/2629312
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Eppstein, D. (2016). k-Best Enumeration. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_733
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_733
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering