Last revision: 2011-05-01
[bibtex] [dvi]

1. Ilan Adler, Alan J. Hoffman and Ron Shamir
   Monge and Feasibility Sequences in General Flow Problems
   Discrete Applied Mathematics
   44(1-3) 1993
   Pages 21-38
   [pdf] (AdlerHS93)
    
2. Conference version:
   Pankaj K. Agarwal, Sandeep Sen.
   Selection in Monotone Matrices and Computing the kth Nearest Neighbors.
   Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, SWAT 1994.
   Aarhus, Denmark. 06-08 July 1994.
   Lecture Notes in Computer Science, Volume 824, 1994. [web]
   Pages 13-24.
   [web] [pdf]
   Journal version:
   Pankaj K. Agarwal, Sandeep Sen.
   Selection in Monotone Matrices and Computing kth Nearest Neighbors.
   Journal of Algorithms.
   Volume 20, Issue 3, May 1996.
   Pages 581-601.
   [web] [pdf] [ps] (AgSe96) [computational geometry]
    
3. Conference version:
   Alok Aggarwal, Amotz Bar-Noy, Samir Khuller, Dina Kravets, Baruch Schieber.
   Efficient Minimum Cost Matching Using Quadrangle Inequality.
   Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992.
   Pittsburgh, Pennsylvania, United States. 24-27 October 1992.
   Pages 583-592.
   [web] [pdf] (AgBa92+-conf)
   Journal version:
   Alok Aggarwal, Amotz Bar-Noy, Samir Khuller, Dina Kravets, Baruch Schieber.
   Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality.
   Journal of Algorithms.
   Volume 19, Issue 1, July 1995.
   Pages 116-143.
   [web] [pdf] (AgBa95+) [transportation]
    
4. Alok Aggarwal, Maria Klawe.
   Applications of Generalized Matrix Searching to Geometric Algorithms.
   Discrete Applied Mathematics.7
   Volume 27, Issues 1-2, May 1990.
   Pages 3-23.
   [web] [pdf] (AgKl90) [computational geometry]
    
5. Conference version:
   Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter Shor, Robert Wilber.
   Geometric Applications of a Matrix Searching Algorithm.
   Proceedings of the 2nd Annual Symposium on Computational Geometry, SCG 1986.
   Yorktown Heights, New York, United States. 02-04 June 1986.
   Pages 285-292.
   [web] [pdf] (AgKl86+-conf)
   Journal version:
   Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, Robert E. Wilber.
   Geometric Applications of a Matrix-Searching Algorithm.
   Algorithmica.
   Volume 2, Issue 1, March 1987.
   Pages 195-208.
   [web] [pdf] (AgKl87+) [computational geometry]
    
6. Alok Aggarwal, Dina Kravets
   A Linear Time Algorithm for Finding all Farthest Neighbors in a Convex Polygon
   Information Processing Letters
   31(1): 17-20 (1989)
   [pdf] (AgKr89)
    
7. Conference version:
   Alok Aggarwal, Dina Kravets, James K. Park, Sandeep Sen.
   Parallel Searching in Generalized Monge Arrays with Applications (Extended Abstract).
   Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1990.
   Island of Crete, Greece. 02-06 July 1990.
   Pages 259-268.
   [web] [pdf] (AgKr90+-conf)
   Journal version:
   Alok Aggarwal, Dina Kravets, James K. Park, Sandeep Sen.
   Parallel Searching in Generalized Monge Arrays.
   Algorithmica.
   Volume 19, Issue 3, November 1997.
   Pages 291-317.
   [web] [pdf] (AgKr97+) [computational geometry, coding]
    
8. Alok Aggarwal, James K. Park.
   Notes on Searching in Multidimensional Monotone Arrays.
   Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FOCS 1988.
   White Plains, New York, United States. 24-26 October 1988.
   Pages 497-512.
   [web] [pdf] (AgPa88-conf) [computational geometry]
    
9. Alok Aggarwal, James K. Park.
   Improved Algorithms for Economic Lot Size Problems.
   Operations Research.
   Volume 41, Issue 3, May-June 1993.
   Pages 549-571.
   [pdf] (AgPa93) [operations research]
    
10. Conference version:
    Alok Aggarwal, Baruch Schieber, Takeshi Tokuyama.
    Finding a Minimum Weight K-Link Path in Graphs with Monge Property and Applications.
    Proceedings of the 9th Annual Symposium on Computational Geometry, SCG 1993.
    San Diego, California, United States. 18-21 May 1993.
    Pages 189-197.
    [web] [pdf] (AgSc93+-conf)
    Journal version:
    Alok Aggarwal, Baruch Schieber, Takeshi Tokuyama.
    Finding a Minimum-Weight k-Link Path in Graphs with the Concave Monge Property and Applications.
    Discrete and Computational Geometry.
    Volume 12, 1994.
    Pages 263-280.
    [pdf] (AgSc94+) [computational geometry]
     
11. Conference Version
    Alok Aggarwal, Takeshi Tokuyama.
    Consecutive Interval Query and Dynamic Programming on Intervals.
    Proceedings of the 4th International Symposium on Algorithms and Computation, ISAAC 1993.
    Hong Kong. 15-17 December 1993.
    Lecture Notes in Computer Science, Volume 762, 1993. [web]
    Pages 466-475.
    [web] [pdf] (AgTo93-conf) [computational geometry]
    Journal Version
    Alok Aggarwal, Takeshi Tokuyama
    Consecutive Interval Query and Dynamic Programming on Intervals
    Discrete Applied Mathematics
    Volume 85, Issue 1, 1 June 1998
    Pages 1-24
    [web] [pdf] (AgTo98)
     
12. Susanne Albers, Peter Brucker.
    The Complexity of One-Machine Batching Problems.
    Discrete Applied Mathematics.
    Volume 47, Issue 2, 30 November 1993.
    Pages 87-107.
    [web] [pdf] (AlBr93) [scheduling]
     
13. Alberto Apostolico, Mikhail Atallah, Lawrence Larmore, Scott McFaddin.
    Efficient Parallel Algorithms for String Editing and Related Problems.
    SIAM Journal on Computing.
    Volume 19, Issue 5, October 1990.
    Pages 968-988.
    [web] [pdf] (ApAt90+)
     
14. Abdullah N. Arslan, Omer Egecioglu.
    Dynamic Programming Based Approximation Algorithms for Sequence Alignment with Constraints.
    INFORMS Journal on Computing.
    Volume 16, Issue 4, Fall 2004.
    Pages 441-458.
    [web] [pdf] (ArEg04)
     
15. Takao Asano.
    Dynamic Programming on Intervals.
    Proceedings of the 2nd International Symposium on Algorithms, ISA 1991.
    Taipei, Republic of China. 16-18 December 1991.
    Lecture Notes in Computer Science, Volume 557, 1991. [web]
    Pages 199-207.
    [web] [pdf] (As91-conf)
     
16. Mikhail J. Atallah.
    Parallel Techniques for Computational Geometry. [Survey]
    Proceedings of the IEEE. (Note: This is a journal)
    Volume 80, Issue 9, September 1992.
    Pages 1435-1448.
    [web] [pdf] (At92)
     
17. Mikhail J. Atallah.
    A Faster Parallel Algorithm for a Matrix Searching Problem.
    Algorithmica.
    Volume 9, Issue 2, February 1993.
    Pages 156-167.
    [web] [pdf] (At93)
     
18. Conference version:
    Mikhail J. Atallah, S. Rao Kosaraju.
    An Efficient Parallel Algorithm for the Row Minima of a Totally Monotone Matrix.
    Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991.
    San Francisco, California, United States. 28-30 January 1991.
    Pages 394-403.
    [web] [pdf]
    Journal version:
    Mikhail J. Atallah, S. Rao Kosaraju.
    An Efficient Parallel Algorithm for the Row Minima of a Totally Monotone Matrix.
    Journal of Algorithms.
    Volume 13, Issue 3, September 1992.
    Pages 394-413.
    [web] [pdf] (AtKo92)
     
19. Mikhail J. Atallah, S. Rao Kosaraju, Lawrence L. Larmore, Gary L. Miller, Shang-Hua Teng.
    Constructing Trees in Parallel.
    Proceedings of the 1st Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1989.
    Santa Fe, New Mexico, United States. 18-21 June 1989.
    Pages 421-431.
    [web] [pdf] [ps] (AtKo89+-conf) [coding, software (optimal binary search tree), formal language]
     
20. Vincenzo Auletta, Domenico Parente, Giuseppe Persiano.
    Placing Resources on a Growing Line.
    Journal of Algorithms.
    Volume 26, Issue 1, January 1998.
    Pages 87-100.
    [missing from the official website] [ps] (AuPa98+) [graph (median)]
     
21. László Babai and Pedro Felzenszwalb
    Computing Rank Convolutions with a Mask
    To Appear in ACM Transactions on Algorithms (2009)
    [pdf] (BaFe09) [min convolutions - vision]
     
22. Brenda S. Baker, Raffaele Giancarlo
    Sparse Dynamic Programming for Longest Common Subsequence from Fragments
    J. Algorithms 42(2): 231-254 (2002)
    [pdf] (BaGi02)
     
23. Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang.
    Online Dynamic Programming Speedups
    Proceedings of the 4th International Workshop on Approximation and Online Algorithms, WAOA 2006.
    Zurich, Switzerland. 14-15 September 2006.
    Lecture Notes in Computer Science, Volume 4368, 2007. [web]
    Pages 43-54.
    [web] [pdf] (BaGo06+-conf)
    Journal Version
    Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang
    Online Dynamic Programming Speedups
    Theory of Computing Systems
    Volume 45, 2009
    Pages 429–445
    [web][pdf] (BGY09)
     
24. Amotz Bar-Noy, Richard E. Ladner.
    Efficient Algorithms for Optimal Stream Merging for Media-on-Demand.
    SIAM Journal on Computing.
    Volume 33, Issue 5, 2004.
    Pages 1011-1034.
    [web] [pdf] [pdf] [ps] (BaLa04) [networking]
     
25. Wolfgang W. Bein, Peter Brucker, Lawrence L. Larmore, James K. Park.
    Fast Algorithms with Algebraic Monge Properties.
    Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002.
    Warsaw, Poland. 26-30 August 2002.
    Lecture Notes in Computer Science, Volume 2420, 2002. [web]
    Pages 104-117.
    [web] [pdf] (BeBr02+-conf) [graph (bottleneck shortest path, bottleneck tsp), software (paragraph formation)]
     
26. Wolfgang W. Bein, Peter Brucker, Lawrence L. Larmore, James K. Park.
    The Algebraic Monge Property and Path Problems.
    Discrete Applied Mathematics.
    Volume 145, Issue 3, 30 January 2005.
    Pages 455-464.
    [web] [pdf] (BeBr05+) [graph (bottleneck shortest path, bottleneck tsp)]
     
27. Wolfgang W. Bein, Peter Brucker, James K. Park, Pramod K. Pathak.
    A Monge Property for the d-Dimensional Transportation Problem.
    Discrete Applied Mathematics.
    Volume 58, Issue 2, 24 March 1995. (Workshop on Discrete Algorithms)
    Pages 97-109.
    [web] [pdf] (BeBr95+) [transportation]
     
28. Wolfgang W. Bein, Pramod K. Pathak.
    A Characterization of the Monge Property and Its Connection to Statistics.
    Demonstratio Mathematica.
    Volume 29, Issue 2, 1996.
    Pages 451-457.
    [ps] (BePa96) [statistics]
     
29. M. Bellmore, G. L. Nemhauser.
    The Traveling Salesman Problem: A Survey.
    Operations Research.
    Volume 16, Issue 3, May-June 1968.
    Pages 538-558.
    [pdf] (BeNe68)
     
30. Norbert Blum
    Speeding Up Dynamic Programming without Omitting any Optimal Solution and Some Applications in Molecular Biology
    J. Algorithms
    35(2) (2000)
    Pages 129-168
    [pdf] (Blum2000)
     
31. Hans L. Bodlaender, Jan Arne Telle.
    Space-Efficient Construction Variants of Dynamic Programming.
    Nordic Journal of Computing.
    Volume 11, Issue 4, 2004.
    Pages 374-385.
    [pdf] [pdf] [ps] (BoTe04)
     
32. Al Borchers, Prosenjit Gupta.
    Extending the Quadrangle Inequality to Speed-up Dynamic Programming.
    Information Processing Letters.
    Volume 49, Issue 6, 22 March 1994.
    Pages 287-290.
    [web] [pdf] (BoGu94) [graph (steiner tree)]
     
33. Phillip G. Bradford.
    Parallel Dynamic Programming.
    PhD Thesis. Indiana University.
    December 1994.
    [ps] (Br94)
     
34. Phillip G. Bradford, Rudolf Fleischer, Michiel Smid.
    More Efficient Parallel Totally Monotone Matrix Searching.
    Journal of Algorithms.
    Volume 23, Issue 2, May 1997.
    Pages 386-400.
    [web] [pdf] (BrFl97+)
     
35. Conference version:
    Phillip G. Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter.
    Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property.
    Proceedings of the 6th Annual European Symposium on Algorithms, ESA 1998.
    Venice, Italy. 24-26 August 1998.
    Lecture Notes in Computer Science, Volume 1461, 1998. [web]
    Pages 43-54.
    [web] [pdf] [ps]
    Journal version:
    Phillip G. Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter.
    Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property.
    Journal of Algorithms.
    Volume 42, Issue 2, February 2002.
    Pages 277-303.
    [web] [pdf] [ps] (BrGo02+) [coding]
     
36. Conference version:
    Phillip G. Bradford, Gregory J. E. Rawlins, Gregory E. Shannon.
    Efficient Matrix Chain Ordering in Polylog Time (Extended Abstract).
    Proceedings of the 8th International Parallel Processing Symposium, IPPS 1994.
    Cancun, Mexico. 26-29 April 1994.
    Pages 234-241.
    [web] [pdf]
    Journal version:
    Phillip G. Bradford, Gregory J. E. Rawlins, Gregory E. Shannon.
    Efficient Matrix Chain Ordering in Polylog Time.
    SIAM Journal on Computing.
    Volume 27, Issue 2, April 1998.
    Pages 466-490.
    [web] [pdf] [ps] (BrRa98+)
     
37. Rainer E. Burkard.
    (Generalized) Convexity and Discrete Optimization.
    Proceedings of the 7th International Symposium on Generalized Convexity and Generalized Monotonicity (Invited Paper).
    Hanoi. 27-31 August 2002.
    Andrew Eberhand, Nicolas Hadjisavvas, Dinh The Luc (editors).
    Generalized Convexity, Generalized Monotonicity and Applications.
    Series: Nonconvex Optimization and Its Applications, Volume 77.
    Springer Science+Business Media Inc., New York, United States of America. 2005.
    Pages 23-37.
    [springer] [amazon] [pdf] (Bu05)
     
38. Conference version:
    Rainer E. Burkard, Eranda Cela, Gunter Rote, Gerhard J. Woeginger.
    The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases.
    Proceedings of the 5th International Conference on Integer Programming and Combinatorial Optimization, IPCO 1996.
    Vancouver, British Columbia, Canada. 03-05 July 1996.
    Lecture Notes in Computer Science, Volume 1084, 1996. [web]
    Pages 204-218.
    [web] [pdf]
    Journal version:
    Rainer E. Burkard, Eranda Cela, Gunter Rote, Gerhard J. Woeginger.
    The Quadratic Assignment Problem with a Monotone Anti-Monge and a Symmetric Toeplitz Matrix: Easy and Hard Cases.
    Mathematical Programming.
    Volume 82, Issue 1-2, June 1998.
    Pages 125-158.
    [web] [pdf] [pdf] [ps] (BuCe98+) [graph (turbine, tsp), software (optimal binary search tree on a tape)]
     
39. Rainer E. Burkard, Vladimir G. Deineko.
    On the Traveling Salesman Problem with a Relaxed Monge Matrix.
    Information Processing Letters.
    Volume 67, Issue 5, 15 September 1998.
    Pages 231-237.
    [web] [pdf] (BuDe98) [graph (tsp)]
     
40. Rainer E. Burkard, Vladimir G. Deineko, Rene van Dal, Jack A. A. van der Veen, Gerhard J. Woeginger.
    Well-Solvable Special Cases of the TSP: A Survey.
    SIAM Review.
    Volume 40, Issue 3, January 1998.
    Pages 496-546.
    [web] [pdf] [ps] (BuDe98+)
     
41. Rainer E. Burkard, Vladimir G. Deineko, Gerhard J. Woeginger.
    The Travelling Salesman Problem on Permuted Monge Matrices.
    Journal of Combinatorial Optimization.
    Volume 2, Issue 4, 1999.
    Pages 333-350.
    [web] [pdf] [ps] (BuDe99+) [graph (tsp)]
     
42. Rainer E. Burkard, Bettina Klinz, Rudiger Rudolf.
    Perspectives of Monge Properties in Optimization. [Survey]
    Discrete Applied Mathematics.
    Volume 70, Issue 2, 24 September 1996.
    Pages 95-161.
    [web] [pdf] [ps] (BuKl96+)
     
43. Rainer E. Burkard, Wolfgang Sandholzer.
    Efficiently Solvable Special Cases of Bottleneck Travelling Salesman Problems.
    Discrete Applied Mathematics.
    Volume 32, Issue 1, 11 June 1991.
    Pages 61-76.
    [web] [pdf] (BuSa91)
     
44. Conference version:
    Samuel R. Buss, Peter N. Yianilos.
    Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.
    Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1994.
    Arlington, Virginia, United States. 23-25 January 1994.
    Pages 65-76.
    [web] [pdf]
    Journal version:
    Samuel R. Buss, Peter N. Yianilos.
    Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.
    SIAM Journal on Computing.
    Volume 27, Issue 1, February 1998.
    Pages 170-201.
    [web] [pdf] [ps] (BuYi98) [graph (matching)]
     
45. Kun-Mao Chao, Ross C. Hardison, Webb Miller.
    Recent Developments in Linear-Space Alignment Methods: A Survey.
    Journal of Computational Biology.
    Volume 1, Issue 4, Winter 1994.
    Pages 271-292.
    [pdf] [pdf] [ps] (ChHa94+)
     
46. Conference version:
    Danny Z. Chen, Ovidiu Daescu, Xiaobo Sharon Hu, Jinhui Xu.
    Finding an Optimal Path without Growing the Tree.
    Proceedings of the 6th Annual European Symposium on Algorithms, ESA 1998.
    Venice, Italy. August 1998.
    Lecture Notes in Computer Science, Volume 1461, 1998. [web]
    Pages 356-367.
    [web] [pdf] [ps]
    Journal version:
    Danny Z. Chen, Ovidiu Daescu, Xiaobo Sharon Hu, Jinhui Xu.
    Finding an Optimal Path without Growing the Tree.
    Journal of Algorithms.
    Volume 49, Issue 1, October 2003.
    Pages 13-41.
    [web] [pdf] (ChDa03+)
     
47. Victor Chepoi.
    On Distances in Benzenoid Systems.
    Journal of Chemical Information and Computer Sciences.
    Volume 36, Issue 6, November 1996.
    Pages 1169-1172.
    [web] [pdf] [ps] (Ch96)
     
48. Maxime Crochemore, Gad M. Landau, Michal Ziv-Ukelson.
    A Sub-quadratic Sequence Alignment Algorithm for Unrestricted Cost Matrices.
    Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002.
    San Francisco, California. 06-08 January 2002.
    Pages 679-688.
    [web] [pdf] [ps] (CrLa02+-conf)
     
49. Brian C. Dean.
    Speeding up Stochastic Dynamic Programming with Zero-Delay Convolution.
    Journal of Optimization Theory and Applications.
    (Submitted)
    [pdf] (De-Submit)
     
50. Brian C. Dean
    Algorithms for Minimum-Cost Paths in Time-Dependent Networks with Waiting Policies
    Networks
    44(1) 2004
    Pages 41-46
    [web] [pdf] (Dean04)
     
51. Vladimir G. Deineko, Bettina Klinz, Gerhard J. Woeginger.
    Four Point Conditions and Exponential Neighborhoods for Symmetric TSP.
    Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006.
    Miami, Florida. 22-26 January 2006.
    Pages 544-553.
    [web] [pdf] (Dekl06+-conf) [graph (tsp)]
     
52. Vladimir G. Deineko, George Steiner, Zhihui Xue.
    Robotic-Cell Scheduling: Special Polynomially Solvable Cases of the Traveling Salesman Problem on Permuted Monge Matrices.
    Journal of Combinatorial Optimization.
    Volume 9, Issue 4, June 2005.
    Pages 381-399.
    [web] [pdf] (DeSt05+) [scheduling, graph (tsp)]
     
53. Vladimir G. Deineko, Alexander Tiskin.
    One-Sided Monge TSP Is NP-Hard.
    Proceedings of the International Conference on Computational Science and Its Applications, Part III, ICCSA 2006.
    Glasgow, United Kingdom. 08-11 May 2006.
    Lecture Notes in Computer Science, Volume 3982, 2006. [web]
    Pages 793-801.
    [web] [pdf] (DeTi06-conf) [graph (tsp)]
     
54. Vitali M. Demidenko.
    Conic Characterization of Monge Matrices.
    Cybernetics and Systems Analysis.
    Volume 40, Issue 4, July 2004.
    Pages 537-546.
    [web] [pdf] (De04) [optimization]
     
55. Eric V. Denardo
    Contraction Mappings in the Theory Underlying Dynamic Programming
    SIAM Review, Vol. 9, No. 2. (Apr.1967)
    pp. 165-177.
    [pdf] (Denado67)
     
56. T. Dudas and R. Rudolf
    Spanning trees and shortest paths in Monge graphs
    Computing
    Volume 60 , Issue 2 (1998)
    Pages: 109 - 119
    [pdf] (DuRu98)
     
57. Sorina Dumitrescu
    Faster algorithm for designing optimal prefix-free codes with unequal letter costs
    Fundamenta Informaticae
    73 (1-2), pp. 107-117
    2006 [pdf] (Dumit06)
     
58. Sorina Dumitrescu, Xiaolin Wu.
    Algorithms for Optimal Multi-Resolution Quantization.
    Journal of Algorithms.
    Volume 50, Issue 1, January 2004.
    Pages 1-22.
    [web] [pdf] (DuWu04) [signal processing]
     
59. Sorina Dumitrescu, Xiaolin Wu, Zhe Wang.
    Globally Optimal Uneven Error-Protected Packetization of Scalable Code Streams.
    IEEE Transactions on Multimedia.
    Volume 6, Issue 2, April 2004.
    Pages 230-239.
    [web] [pdf] (DuWu04+) [networking, coding]
     
60. David Eppstein.
    Efficient Algorithms for Sequence Analysis with Concave and Convex Gap Costs.
    PhD Thesis, Columbia University.
    1989.
    [pdf] (Ep89)
     
61. David Eppstein.
    Sequence Comparison with Mixed Convex and Concave Costs.
    Journal of Algorithms.
    Volume 11, Issue 1, March 1990.
    Pages 85-101.
    [web] [pdf] [pdf] (Ep90) [string (biology, geology, speech recognition)]
     
62. David Eppstein, Zvi Galil, Raffaele Giancarlo.
    Speeding up Dynamic Programming.
    Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FOCS 1988.
    White Plains, New York, United States. 24-26 October 1988.
    Pages 488-496.
    [web] [pdf] [pdf] (EpGa88+-conf) [string (biology, geology, speech recognition)]
     
63. Conference version:
    David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano.
    Sparse Dynamic Programming.
    Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990.
    San Francisco, California, United States. 22-24 January 1990.
    Pages 513-522.
    [web] [pdf] (EpGa90+-conf)
    Journal version (1):
    David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano.
    Sparse Dynamic Programming I: Linear Cost Functions.
    Journal of the ACM.
    Volume 39, Issue 3, July 1992.
    Pages 519-545.
    [web] [pdf] (EpGa92a+)
    Journal version (2):
    David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano.
    Sparse Dynamic Programming II: Convex and Concave Cost Functions.
    Journal of the ACM.
    Volume 39, Issue 3, July 1992.
    Pages 546-567.
    [web] [pdf] (EpGa92b+)
     
64. Awi Federgruen and Michal Tzur
    A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time
    Management Science
    Volume 37, Issue 8, August 1991
    Pages 909 - 925
    [web] [pdf] (FeTz91)
     
65. Awi Federgruen and Michal Tzur
    Fast solution and detection of minimal forecast horizons in dynamic programs with a single indicator of the future – applications to dynamic lot-sizing models
    Management Science
    41(5):874–893, 1995
    [web] [pdf] (FeTz95)
     
66. P.F. Felzenszwalb, D.P. Huttenlocher
    Distance transforms of sampled functions
    Tech. Rep. TR2004-1963
    Cornell Computing and Information Science (Sep. 2004).
    [pdf] (FeHu04) [vision]
     
67. Conference version:
    Rudolf Fleischer, Mordecai J. Golin, Yan Zhang.
    Online Maintenance of k-Medians and k-Covers on a Line.
    Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, SWAT 2004.
    Humlebaek, Denmark. 8-10 July 2004.
    Lecture Notes in Computer Science, Volume 3111, 2004. [web]
    Pages 102-113.
    [web] [pdf]
    Journal version:
    Rudolf Fleischer, Mordecai J. Golin, Yan Zhang.
    Online Maintenance of k-Medians and k-Covers on a Line.
    Algorithmica.
    Volume 45, Issue 4, August 2006.
    Pages 549-567.
    [web] [pdf] (FlGo06+)
     
68. Zvi Galil, Raffaele Giancarlo.
    Speeding up Dynamic Programming with Applications to Molecular Biology.
    Theoretical Computer Science.
    Volume 64, Issue 1, April 1989.
    Pages 107-118.
    [web] [pdf] (GaGi89) [string]
     
69. Zvi Galil, Kunsoo Park.
    A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming.
    Information Processing Letters.
    Volume 33, Issue 6, 10 February 1990.
    Pages 309-311.
    [web] [pdf] (GaPa90) [string (biology, geology, speech recognition)]
     
70. Zvi Galil, Kunsoo Park.
    Dynamic Programming with Convexity, Concavity and Sparsity.
    Theoretical Computer Science.
    Volume 92, Issue 1, 6 January 1992.
    Pages 49-76.
    [web] [pdf] [pdf] (GaPa92) [string (biology)]
     
71. Zvi Galil, Kunsoo Park.
    Parallel Algorithms for Dynamic Programming Recurrences with More than O(1) Dependency.
    Journal of Parallel and Distributed Computing.
    Volume 21, Issue 2, May 1994.
    Pages 213-222.
    [web] [ps] (GaPa94) [string (biology, geology, speech recognition), software (minimum height b-tree, chain matrix multiplication, optimal binary search tree), computational geometry]
     
72. Alfredo Garcia, Pedro Jodra, Javier Tejel.
    An Efficient Algorithm for On-Line Searching of Minima in Monge Path-Decomposable Tridimensional Arrays.
    Information Processing Letters.
    Volume 68, Issue 1, 15 October 1998.
    Pages 3-9.
    [web] [pdf] (GaJo98+) [string (biology), operations research, computational geometry, graph (tsp)]
     
73. William G. Gardner.
    Efficient Convolution without Input-Output Delay.
    Journal of the Audio Engineering Society.
    Volume 42, Issue 3, March 1995.
    Pages 127-136.
    [pdf] (Ga95)
     
74. Martin Gavalec, Jan Plavka.
    Computing an Eigenvector of a Monge Matrix in Max-Plus Algebra.
    Mathematical Methods of Operations Research.
    Volume 63, Issue 3, July 2006.
    Pages 543-551.
    [web] [pdf] (GaPl06) [graph (tsp)]
     
75. Edgar N. Gilbert, Edward F. Moore.
    Variable Length Encodings.
    Bell System Technical Journal.
    Volume 38, 1959.
    Pages 933-967.
    [pdf] (GiMo59)
     
76. L. Gotlieb.
    Optimal Multi-Way Search Trees.
    SIAM Journal on Computing.
    Volume 10, Issue 3, August 1981.
    Pages 422-433.
    [web] [pdf] (Go81)
     
77. L. Gotlieb, Derick Wood.
    The Construction of Optimal Multiway Search Trees and the Monotonicity Principle.
    International Journal of Computer Mathematics, Section A: Programming Theory and Methods.
    Volume 9, Issue 1, 1981.
    Pages 17-24.
    [pdf] (GoWo81)
     
78. Oktay Gunluk.
    A Pricing Problem under Monge Property.
    IBM Research Report, RC23823, IBM Research Division, Thomas J. Watson Research Center, 2005.
    [pdf] [pdf] [ps] (Gu05) [economics]
     
79. Dan Gusfield.
    Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology.
    First Edition, Cambridge University Press, January 1997.
    [web] (Gu97)
     
80. Nir Halman, Diego Klabjan, Chung-Lun Li, James Orlin, and David Simchi-Levi.
    Fully polynomial time approximation schemes for stochastic dynamic programs
    In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA '08)
    [pdf] (Halmanetal08)
     
81. Refael Hassin, Arie Tamir.
    Improved Complexity Bounds for Location Problems on the Real Line.
    Operations Research Letters.
    Volume 10, Issue 7, October 1991.
    Pages 395-402.
    [web] [ps] (HaTa91) [graph (median)]
     
82. Conference version:
    Xin He, Zhi-Zhong Chen.
    Shortest Path in Complete Bipartite Digraph Problem and its Applications.
    Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1997.
    New Orleans, Louisiana, United States. 05-07 January 1997.
    Pages 230-238.
    [web] [pdf] (HeCh97-conf)
    Journal version:
    Xin He, Zhi-Zhong Chen.
    An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications.
    SIAM Journal on Computing.
    Volume 29, Issue 1, September 1999.
    Pages 65-80.
    [web] [pdf] [ps] (HeCh99) [graph (shortest path, tsp)]
     
83. Danny Hermelin and Gad M. Landau and Shir Landa and Oren Weimann
    A unified algorithm for accelerating edit-distance computation via text-compression
    Proceedings of the 26th STACS
    2009
    Pages 529-540
    [pdf] (HLLW09)
     
84. Daniel S. Hirschberg.
    A Linear Space Algorithm for Computing Maximal Common Subsequences.
    Communications of the ACM.
    Volume 18, Issue 6, June 1975.
    Pages 341-343.
    [web] [pdf] (Hi75)
     
85. Daniel S. Hirschberg, Lawrence L. Larmore.
    The Least Weight Subsequence Problem.
    SIAM Journal on Computing.
    Volume 16, Issue 4, August 1987.
    Pages 628-638.
    [web] [pdf] (HiLa87a) [software (paragraph formation, minimum height b-tree)]
     
86. Daniel S. Hirschberg, Lawrence L. Larmore.
    New Applications of Failure Functions.
    Journal of the ACM.
    Volume 34, Issue 3, July 1987.
    Pages 616-625.
    [web] [pdf] (HiLa87b)
     
87. Pei-Hao Ho, Arie Tamir and Bang Ye Wu
    Minimum L_k path partitioning- An illustration of the Monge property.
    Operations Research Letters,
    Volume 36, Issue 1 (2008)
    Pages 43-45.
    [pdf]  (HoTaWu08) [has both convex and concave examples of nested Monge]
     
88. Stan van Hoesel, Albert Wagelmans, Bram Moerman
    Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions
    European Journal of Operational Research
    Issue 75, 1994
    312-331
    [pdf]  (HoWaMo94) [An algorithm very similar to Bar-Noy, Golin, Zhang for online Monge]
     
89. Xiaoling Hou, Andras Prekopa.
    Monge Property and Bounding Multivariate Probability Distribution Functions with Given Marginals and Covariances.
    RUTCOR Research Report, RRR 27-2005.
    RUTCOR, Rutgers Center for Operations Research, Rutgers University.
    640 Bartholomew Road, Piscataway, New Jersey. September 2005.
    [pdf] [ps] (HoPr05) [transportation]
     
90. T. C. Hu, Lawrence L. Larmore, J. David Morgenthaler.
    Optimal Integer Alphabetic Trees in Linear Time.
    Proceedings of the 13th Annual European Symposium on Algorithms, ESA 2005.
    Palma de Mallorca, Spain. 3-6 October 2005.
    Lecture Notes in Computer Science, Volume 3669, 2005. [web]
    Pages 226-237.
    [web] [pdf] (HuLa05+-conf)
     
91. T.C. Hu & J. Morgenthaler
    Dynamic Programming and Graph Optimization Problems
    Computers and Mathematics with Applications
    Volume 27, 1994
    Pages 53-53
    [pdf] (HuMo94)
     
92. T. C. Hu, M. T. Shing.
    Computation of Matrix Chain Products. Part I.
    SIAM Journal on Computing.
    Volume 11, Issue 2, May 1982.
    Pages 362-373.
    [web] [pdf] (HuSh82)
     
93. T. C. Hu, M. T. Shing.
    Computation of Matrix Chain Products. Part II.
    SIAM Journal on Computing.
    Volume 13, Issue 2, May 1984.
    Pages 228-251.
    [web] [pdf] (HuSh84)
     
94. T. C. Hu, A. C. Tucker.
    Optimal Computer Search Trees and Variable-Length Alphabetical Codes.
    SIAM Journal on Applied Mathematics.
    Volume 21, Issue 4, December 1971.
    Pages 514-532.
    [web] [pdf] (HuTu71)
     
95. Guan-Shieng Huang, Jia Jie Liu, Yue-Li Wang
    Sequence Alignment Algorithms for Run-Length-Encoded Strings
    Proceedings of 14th Annual International Computing and Combinatorics Conference (COCOON'08)
    Pages 319-330
    [web] [pdf] (HLW08) [Monge Property + Hischberg]
     
96. James W. Hunt and Thomas G. Szymanski
    A Fast Algorithm for Computing Longest Common Subsequences
    Communications of the ACM
    20(5)5, May 1977
    Pages 350-353,
    [web] [pdf] (HuSz77)
     
97. Alon Itai.
    Optimal Alphabetic Trees.
    SIAM Journal on Computing.
    Volume 5, Issue 1, March 1976.
    Pages 9-18.
    [web] [pdf] (It76)
     
98. Marek Karpinski, Lawrence L. Larmore and Wojciech Rytter
    Correctness of Constructing Optimal Alphabetic Trees Revisited
    Theoretical  Computer. Science
    180(1-2) 1997
    pp. 309-324
    [pdf] (KLR97)
     
99. Ali Khajeh-Saeed, Stephen Poole, and J. Blair Perot
    Acceleration of the Smith-Waterman algorithm using single and multiple graphics processors.
    J. Comput. Phys.
    229, 11 (June 2010), 4247-4258.
    DOI=10.1016/j.jcp.2010.02.009 http://dx.doi.org/10.1016/j.jcp.2010.02.009
    [pdf] (KsPP2010)
     
100. Valerie King, Mikkel Thorup.
     A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms.
     Proceedings of the 7th International Conference on Computing and Combinatorics, COCOON 2001.
     Guilin, China. 20-23 August 2001.
     Lecture Notes in Computer Science, Volume 2108, 2001. [web]
     Pages 268-277.
     [web] [pdf] (KiTh01-conf)
      
101. Jeffrey H. Kingston.
     A New Proof of the Garsia-Wachs Algorithm.
     Journal of Algorithms.
     Volume 9, Issue 1, March 1988.
     Pages 129-136.
     [pdf] (Ki88)
      
102. Maria M. Klawe.
     A Simple Linear Time Algorithm for Concave One-Dimensional Dynamic Programming.
     Technical Report 89-16, Department of Computer Science, University of British Columbia, 1989.
     [pdf] (Kl89)
      
103. Conference version:
     Maria M. Klawe.
     Superlinear Bounds on Matrix Searching.
     Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990.
     San Francisco, California, United States. 22-24 January 1990.
     Pages 485-493.
     [web] [pdf] (Kl90-conf)
     Journal version:
     Maria M. Klawe.
     Superlinear Bounds for Matrix Searching Problems.
     Journal of Algorithms.
     Volume 13, Issue 1, March 1992.
     Pages 55-78.
     [web] [pdf] (Kl92)
      
104. Maria M. Klawe, Daniel J. Kleitman.
     An Almost Linear Time Algorithm for Generalized Matrix Searching.
     SIAM Journal on Discrete Mathematics.
     Volume 3, Issue 1, February 1990.
     Pages 81-97.
     [web] [pdf] (KlKl90) [string (biology, geology, speech recognition)]
      
105. Conference version:
     Maria M. Klawe, Brendan Mumey.
     Upper and Lower Bounds on Constructing Alphabetic Binary Trees.
     Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1993.
     Austin, Texas, United States. 25-27 January 1993.
     Pages 185-193.
     [web] [pdf]
     Journal version:
     Maria M. Klawe, Brendan Mumey.
     Upper and Lower Bounds on Constructing Alphabetic Binary Trees.
     SIAM Journal on Discrete Mathematics.
     Volume 8, Issue 4, November 1995.
     Pages 638-651.
     [web] [pdf] [ps] (KlMu95)
      
106. Philip N. Klein and Shay Mozes and Oren and Weimann
     Shortest paths in directed planar graphs with negative lengths: A linear-space O (n log 2 n)-time algorithm
     ACM Transactions on Algorithms
     Volume 6, Issue 2,  2010
     Pages 1-18
     [pdf] (KMW10)
      
107. Bettina Klinz, Rudiger Rudolf, Gerhard J. Woeginger.
     Permuting Matrices to Avoid Forbidden Submatrices.
     Discrete Applied Mathematics.
     Volume 60, Issue 1-3, 23 June 1995.
     Pages 223-248.
     [web] [pdf] (KlRu95+)
      
108. Donald E. Knuth.
     Optimum Binary Search Trees.
     Acta Informatica.
     Volume 1, 1971.
     Pages 14-25.
     [pdf] (Kn71)
      
109. Donald E. Knuth, Michael F. Plass.
     Breaking Paragraphs into Lines.
     Software: Practice and Experience.
     Volume 11, Issue 11, 1981.
     Pages 1119-1184.
     [web] [pdf] (KnPl81)
      
110. Conference version:
     Dina Kravets, James K. Park.
     Selection and Sorting in Totally Monotone Arrays.
     Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990.
     San Francisco, California, United States. 22-24 January 1990.
     Pages 494-502.
     [web] [pdf] (KrPa90-conf)
     Journal version:
     Dina Kravets, James K. Park.
     Selection and Sorting in Totally Monotone Arrays.
     Theory of Computing Systems (formerly Mathematical Systems Theory).
     Volume 24, Issue 3, 1991.
     Pages 201-220.
     [web] [pdf] (KrPa91) [computational geometry, vlsi]
      
111. Bhaskar Krishnamachari, Rung-Hung Gau, Stephen B. Wicker, Zygmunt J. Haas.
     Optimal Sequential Paging in Cellular Wireless Networks.
     Wireless Networks.
     Volume 10, Issue 2, March 2004.
     Pages 121-131.
     [web] [pdf] (KrGa04+)
      
112. Conference version:
     Kwong-Fai Chan, Tak-Wah Lam.
     Finding Least-Weight Subsequences with Fewer Processors.
     Proceedings of the SIGAL International Symposium on Algorithms, ISA 1990. [web]
     Tokyo, Japan. 16-18 August 1990.
     Lecture Notes in Computer Science, Volume 450, 1990.
     Pages 318-327.
     [web] [pdf]
     Journal version:
     Tak Wah Lam, Kwong-Fai Chan.
     Finding Least-Weight Subsequences with Fewer Processors.
     Algorithmica.
     Volume 9, Issue 6, June 1993.
     Pages 615-628.
     [web] [pdf] (LaCh93)
      
113. Gad M. Landau, Michal Ziv-Ukelson.
     On the Common Substring Alignment Problem.
     Journal of Algorithms.
     Volume 41, Issue 2, November 2001.
     Pages 338-359.
     [web] [pdf] (LaZi01)
      
114. Conference version:
     Lawrence L. Larmore, Daniel S. Hirschberg.
     Length-Limited Coding.
     Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990.
     San Francisco, California, United States. 22-24 January 1990.
     Pages 310-318.
     [web] [pdf] (LaHi90-conf)
     Journal version:
     Lawrence L. Larmore, Daniel S. Hirschberg.
     A Fast Algorithm for Optimal Length-Limited Huffman Codes.
     Journal of the ACM.
     Volume 37, Issue 3, July 1990.
     Pages 464-473.
     [web] [pdf] [ps] (LaHi90)
      
115. Lawrence L. Larmore, Teresa M. Przytycka.
     Parallel Construction of Trees with Optimal Weighted Path Length.
     Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1991.
     Hilton Head, South Carolina, United States. 21-24 July 1991.
     Pages 71-80.
     [web] [pdf] (LaPr91-conf)
      
116. Conference version:
     Lawrence L. Larmore, Baruch Schieber.
     On-line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure.
     Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990.
     San Francisco, California, United States. 22-24 January 1990.
     Pages 503-512.
     [web] [pdf] (LaSc90-conf)
     Journal version:
     Lawrence L. Larmore, Baruch Schieber.
     On-line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure.
     Journal of Algorithms.
     Volume 12, Issue 3, September 1991.
     Pages 490-515.
     [web] [pdf] [ps] (LaSc91) [string (biology)]
      
117. Chin Lung Lu, Yen Pin Huang.
     A Memory-Efficient Algorithm for Multiple Sequence Alignment with Constraints.
     Bioinformatics  (formerly Computer Applications in the Biosciences).
     Volume 21, Issue 1, January 2005.
     Pages 20-30.
     [web] [pdf] (LuHu05)
      
118. Yves Lucet
     New Sequential Exact Euclidean Distance Transform Algorithms Based on Convex Analysis
     Image and Vision Computing
     27(1-2) 2009
     Pages 37-44
     [web]  [pdf]  (Lucet09) [vision]
      
119. Ion I. Mandoiu.
     Optimum Extensions of Prefix Codes.
     Information Processing Letters.
     Volume 66, Issue 1, 15 April 1998.
     Pages 35-40.
     [web] [pdf] [ps] (Ma98) [coding]
      
120. Conference version:
     Yishay Mansour, James K. Park, Baruch Schieber, Sandeep Sen.
     Improved Selection on Totally Monotone Arrays.
     Proceedings of the 11th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 1991.
     New Delhi, India. 17-19 December 1991.
     Lecture Notes in Computer Science, Volume 560, 1991. [web]
     Pages 347-359.
     [web] [pdf] (MaPa91+-conf)
     Journal version:
     Yishay Mansour, James K. Park, Baruch Schieber, Sandeep Sen.
     Improved Selection in Totally Monotone Arrays.
     International Journal on Computational Geometry & Applications.
     Volume 3, Issue 2, June 1993.
     Pages 115-132.
     [web] [pdf] (MaPa93+) [computational geometry]
      
121. William J. Masek and Mike Paterson
     A Faster Algorithm Computing String Edit Distances
     William J. Masek and Mike Paterson
     J. Comput. Syst. Sci. 20(1) 1980
     pages 18-31
     [pdf] 
      
122. J. Ian Munro, Raul J. Ramirez.
     Reducing Space Requirements for Shortest Path Problems.
     Operations Research.
     Volume 30, Issue 5, September - October 1982.
     Pages 1009-1013.
     [pdf] (MuRa82)
      

123. Eugene W. Myers, Webb Miller.
     Optimal Alignments in Linear Space.
     Bioinformatics (formerly Computer Applications in the Biosciences).
     Volume 4, Issue 1, March 1988.
     Pages 11-17.
     [web] [pdf] [pdf] [ps] (MyMi88)
      

124. W. Miller and E. W. Myers
     Sequence comparison with concave weighting functions
     Bulletin of Mathematical Biology
     50(2):97-120 1988
     [pdf] (MiMy88)
      

125. Koji Nakano, Stephan Olariu.
     An Efficient Algorithm for Row Minima Computations on Basic Reconfigurable Meshes.
     IEEE Transactions on Parallel and Distributed Systems.
     Volume 9, Issue 6, June 1998.
     Pages 561-569.
     [web] [pdf] (NaOl98) [vlsi, graph (facility location)]
      
126. James K. Park.
     The Monge Array: An Abstraction and Its Applications. [Survey]
     PhD Thesis, Massachusetts Institute of Technology.
     June 1991.
     [pdf] (Pa91)
      
127. James K. Park
     A Special Case of the n-Vertex Traveling-Salesman Problem that can be Solved in O(n) Time
     Information Processing Letters
     40(5): 247-254 (1991) [pdf] (Park91_TSP)
      
128. D. Stott Parker, Prasad Ram.
     The Construction of Huffman Codes is a Submodular ("Convex") Optimization Problem over a Lattice of Binary Trees.
     SIAM Journal on Computing.
     Volume 28, Issue 5, 1999.
     Pages 1875-1905.
     [web] [pdf] [ps] (PaRa99) [coding]
      
129. Conference version:
     Michal Parnas, Dana Ron, Ronitt Rubinfeld.
     On Testing Convexity and Submodularity.
     Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, RANDOM 2002.
     Cambridge, MA, USA. 13-15 September 2002.
     Lecture Notes in Computer Science, Volume 2483, 2002. [web]
     Pages 11-25.
     [web] [pdf]
     Journal version:
     Michal Parnas, Dana Ron, Ronitt Rubinfeld.
     On Testing Convexity and Submodularity.
     SIAM Journal on Computing.
     Volume 32, Issue 5, 2003.
     Pages 1158-1184.
     [web] [pdf] [ps] [ps] (PaRo03+)
      
130. U. Pferschy, R. Rudolf and G.J. Woeginger
     Monge matrices make maximization manageable
     Operations Research Letters
     16, 1994, 245--254
     [pdf] (PRW94) [min-weight binary-k-matchings, max-cut, longest paths in bipartite graphs]
      
131. Conference version:
     Maurice Queyranne, Frits C. R. Spieksma, Fabio Tardella.
     A General Class of Greedily Solvable Linear Programs.
     Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, IPCO 1993.
     Erice, Italy. 29 April - 01 May 1993.
     Pages 385-399.
     [pdf]
     Journal version:
     Maurice Queyranne, Frits C. R. Spieksma, Fabio Tardella.
     A General Class of Greedily Solvable Linear Programs.
     Mathematics of Operations Research.
     Volume 23, Issue 4, November 1998.
     Pages 892-908.
     [pdf] (QuSp98+) [optimization]
      
132. Yuval Rabani, Zvi Galil.
     On the Space Complexity of Some Algorithms for Sequence Comparison.
     Theoretical Computer Science.
     Volume 95, Issue 2, 30 March 1992.
     Pages 231-244.
     [web] [pdf] (RaGa92)
      
133. Sailesh K. Rao, P. Sadayappan, Frank K. Hwang, Peter W. Shor.
     The Rectilinear Steiner Arborescence Problem.
     Algorithmica.
     Volume 7, Issue 2-3, 1992.
     Pages 277-288.
     [web] [pdf] (RaSa92+)
      
134. Rudiger Rudolf, Gerhard J. Woeginger.
     The Cone of Monge Matrices: Extremal Rays and Applications.
     Mathematical Methods of Operations Research (formerly Zeitschrift fur Operations Research).
     Volume 42, Issue 2, June 1995.
     Pages 161-168.
     [web] [pdf] [ps] (RuWo95) [graph (tsp)]
      
135. Amir Said.
     Efficient Alphabet Partitioning Algorithms for Low-Complexity Entropy Coding.
     Proceedings of the Data Compression Conference, DCC'05.
     Volume 00, 29-31 March 2005.
     Pages 183-192.
     [web] [pdf] (Sa05-conf) [coding, multimedia]
      
136. Yoshifumi Sakai.
     A Linear Space Algorithm for Computing a Longest Common Increasing Subsequence.
     Information Processing Letters.
     Volume 99, Issue 5, 15 September 2006.
     Pages 203-207.
     [web] [pdf] (Sa06)
      
137. Conference version:
     Baruch Schieber.
     Computing a Minimum-Weight k-Link Path in Graphs with the Concave Monge Property.
     Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995.
     San Francisco, California, United States. 22-24 January 1995.
     Pages 405-411.
     [web] [pdf] (Sc95-conf)
     Journal version:
     Baruch Schieber.
     Computing a Minimum Weight k-Link Path in Graphs with the Concave Monge Property.
     Journal of Algorithms.
     Volume 29, Issue 2, 1998.
     Pages 204-222.
     [web] [pdf] (Sc98) [computational geometry]
      
138. Rahul Shah.
     Undiscretized Dynamic Programming and Ordinal Embeddings.
     PhD Thesis, New Brunswick, Rutgers, the State University of New Jersey.
     New Brunswick, New Jersey. May 2002.
     [pdf] [ps] (Sh02)
      
139. Rahul Shah, Martin Farach-Colton.
     Undiscretized Dynamic Programming: Faster Algorithms for Facility Location and Related Problems on Trees.
     Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002.
     San Francisco, California. 06-08 January 2002.
     Pages 108-115.
     [web] [pdf] [ps] (ShFa02-conf)
      
140. Anand Srivastav, Hartmut Schroeter, Christoph Michel.
     Approximation Algorithms for Pick-and-Place Robots.
     Annals of Operations Research.
     Volume 107, Issue 1-4, October 2001.
     Pages 321-338.
     [web] [pdf] [ps] (SrSc01+)
      
141. Subhash Suri
     A linear time algorithm for minimum link paths inside a simple polygon
     Computer Vision, Graphics and Image Processing
     35, 1 (July 1986), 99-110.
     [pdf]  (Suri_linear_86)
      
142. Arie Tamir.
     An O(pn²) Algorithm for the p-Median and Related Problems on Tree Graphs.
     Operations Research Letters.
     Volume 19, Issue 2, August 1996.
     Pages 59-64.
     [web] [pdf] (Ta96) [graph (median)]
      
143. Alexandre Tiskin
     Semi-Local String Comparison: Algorithmic Techniques and Applications
     Arxiv 2007
     [web] [pdf] (Tiskin_Arxiv_09) [Monge Matrices]
      
144. Michelle L. Wachs.
     On an Efficient Dynamic Programming Technique of F. F. Yao.
     Journal of Algorithms.
     Volume 10, Issue 4, December 1989.
     Pages 518-530.
     [web] [pdf] (Wa89) [software (optimal binary search tree on a tape)]
      
145. A. P. M. Wagelmans, A. E. Gerodimos
     Improved dynamic programs for some batching problems involving the maximum lateness criterion
     Operations Research Letters
     Volume 27, Issue 3, October 2000
     Pages 109-118.
     [pdf] (WaGe00)
      
146. Robert A. Wagner, Michael J. Fischer.
     The String-to-String Correction Problem.
     Journal of the ACM.
     Volume 21, Issue 1, January 1974.
     Pages 168-173.
     [web] [pdf] (WaFi74)
      
147. Fei-Yue Wang; Huaguang Zhang; Derong Liu;
     Adaptive Dynamic Programming: An Introduction
     IEEE Computational Intelligence Magazine
     vol.4, no.2, pp.39-47, May 2009
     doi: 10.1109/MCI.2009.932261
     [pdf] (WaZhLi2009)
      
148. Oren Weimann
     Accelerating Dynamic Programming
     PhD Thesis, EECS MIT
     2009
     [pdf] (Weimann09)
      
149. Russell L. Wessner.
     Optimal Alphabetic Search Trees with Restricted Maximal Height.
     Information Processing Letters.
     Volume 4, Issue 4, January 1976.
     Pages 90-94.
     [web] [pdf] (We76)
      
150. Robert Wilber.
     The Concave Least-Weight Subsequence Problem Revisited.
     Journal of Algorithms.
     Volume 9, Issue 3, September 1988.
     Pages 418-425.
     [web] [pdf] (Wi88) [software (paragraph formation)]
      
151. Gerhard J.Woeginger
     A comment on scheduling two parallel machines with capacity constraints
     Discrete Optimization
     2(3) 269-272 (2005)
     [pdf] (DP_PTAS_Woe_05)
      
152. Gerhard J. Woeginger.
     Monge Strikes Again: Optimal Placement of Web Proxies in the Internet.
     Operations Research Letters.
     Volume 27, Issue 3, October 2000.
     Pages 93-96.
     [web] [pdf] (Wo00) [networking]
      
153. Xiaolin Wu.
     Optimal Quantization by Matrix Searching.
     Journal of Algorithms.
     Volume 12, Issue 4, December 1991.
     Pages 663-673.
     [web] [pdf] (Wu91) [signal processing]
      
154. I-Hsuan Yang, Chien-Pin Huang, Kun-Mao Chao.
     A Fast Algorithm for Computing a Longest Common Increasing Subsequence.
     Information Processing Letters.
     Volume 93, Issue 5, 16 March 2005.
     Pages 249-253.
     [web] [pdf] (YaHu05+)
      
155. F. Frances Yao.
     Efficient Dynamic Programming Using Quadrangle Inequalities.
     Proceedings of the 12th Annual ACM Symposium on Theory of Computing, STOC 1980.
     Los Angeles, California, United States. 28-30 April 1980.
     Pages 429-435.
     [web] [pdf] (Ya80-conf) [software (optimal binary search tree), formal language, graph (shortest path)]
      
156. F. Frances Yao.
     Speed-up in Dynamic Programming.
     SIAM Journal on Matrix Analysis and Applications (formerly SIAM Journal on Algebraic and Discrete Methods).
     Volume 3, Issue 4, December 1982.
     Pages 532-540.
     [web] [pdf] (Ya82) [software (optimal binary search tree)]