Spanning trees and shortest paths in Monge graphs

DOI10.1007/BF02684360zbMath1088.90539OpenAlexW2003060598MaRDI QIDQ1382772

Rüdiger Rudolf, Tibor Dudás

Publication date: 1998

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02684360

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Combinatorial optimization (90C27) Paths and cycles (05C38) Distance in graphs (05C12)

Related Items (1)

The optimal dispatch of Traffic and Patrol Police Service Platforms

Uses Software

• Algorithm 97

Cites Work

• A note on two problems in connexion with graphs
• Extreme Hamiltonian lines
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Geometric applications of a matrix-searching algorithm
• Monge matrices make maximization manageable
• Balancing minimum spanning trees and shortest-path trees
• Perspectives of Monge properties in optimization
• Special cases of travelling salesman problems and heuristics
• A randomized linear-time algorithm for finding minimum spanning trees
• The concave least-weight subsequence problem revisited

This page was built for publication: Spanning trees and shortest paths in Monge graphs