Dijkstra's algorithm and L-concave function maximization

DOI10.1007/s10107-013-0643-2zbMath1300.90039OpenAlexW1980105916MaRDI QIDQ2248748

Kazuo Murota, Akiyoshi Shioura

Publication date: 27 June 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-013-0643-2

zbMATH Keywords

shortest path problemDijkstra's algorithmsteepest ascent algorithmdiscrete concave function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Related Items

Research on routing algorithm based on limitation arrangement principle in mathematics, A framework of discrete DC programming by discrete convex analysis, Exact bounds for steepest descent algorithms of $L$-convex function minimization, Note on the polyhedral description of the Minkowski sum of two L-convex sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• New algorithms for convex cost tension problem with application to computer vision
• A dual algorithm for submodular flow problems
• Discrete convex analysis
• Extension of M-convexity and L-convexity to polyhedral convex functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Submodular functions and optimization.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm
• Discrete Convex Analysis
• On Steepest Descent Algorithms for Discrete Convex Functions