Extending the quadrangle inequality to speed-up dynamic programming

DOI10.1016/0020-0190(94)90101-5zbMath0801.90122OpenAlexW2104037408MaRDI QIDQ1321816

Al Borchers, Prosenjit Gupta

Publication date: 3 May 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90101-5

zbMATH Keywords

dynamic programmingquadrangle inequalityrectilinear Steiner minimal arborescence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Related Items

Perspectives of Monge properties in optimization

Cites Work

• The rectilinear Steiner arborescence problem