# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Spanning trees and shortest paths in Monge graphs. (English) Zbl 1088.90539
A Monge matrix of order $n$ is an $n×n$ matrix ${\left({c}_{ij}\right)}_{n×n}$ such that ${c}_{ij}+{c}_{kl}\le {c}_{il}+{c}_{kj}$ for all $1\le i, $1\le j, $i\ne j$, $k\ne l$, $i\ne l$, $k\ne j$. A Monge graph is a complete, undirected weighted graph whose distance matrix is a Monge matrix. In this paper, the authors investigate the following three problems on Monge graphs: (1) the minimum spanning tree problem, (2) the problem of computing all-pairs shortest paths, and (3) the problem of determining a minimum weighted 1-to-all shortest path tree. For all three problems best possible algorithms (in terms of complexity) are presented; the complexity of each of them is linear or the square of $n$, the number of vertices of the Monge graphs.
##### MSC:
 90C35 Programming involving graphs or networks 90C27 Combinatorial optimization 05C05 Trees 05C12 Distance in graphs 05C38 Paths; cycles
##### References:
 [1] Aggarwal, A., Klawe, M. M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica2, 195–208 (1987). · Zbl 0642.68078 · doi:10.1007/BF01840359 [2] Burkard, R. E.: Special cases of the travelling salesman problem and heuristics. Acta Math. Appl. Sin.6, 273–288 (1990). [3] Burkard, R. E., Klinz, B., Rudolf, R.: Perspectives of Monge properties in optimization. Discr. Appl. Math.70, 95–161 (1996). · Zbl 0856.90091 · doi:10.1016/0166-218X(95)00103-X [4] Burkard, R. E., Deĭneko, V., van Dal, R., van der Veen, J. A. A., Woeginger, G. J.: Well-solvable cases of the TSP: A survey. SFB-Report No. 52, SFB ’Optimierung und Kontrolle’, Institute of Mathematics, University of Technology, Graz, Austria, December 1995, submitted for publication. [5] Dijkstra, E. W.: A note on two problems in connection with graphs. Numer. Math.1, 269–271 (1959). · Zbl 0092.16002 · doi:10.1007/BF01386390 [6] Floyd, R. W.: Algorithm 97 (Shortest Path). Comm. ACM5, 345 (1962). · doi:10.1145/367766.368168 [7] Fredman, M. L., Tarjan, R. E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach.34, 596–615 (1987). [8] Gabow, H. N., Galil, Z., Spencer, T., Tarjan, R. E.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica6, 109–122 (1986). · Zbl 0608.05027 · doi:10.1007/BF02579168 [9] Khuller, S., Raghavachari, B., Young, N.: Balancing minimum spanning trees and shortest-path trees. Algorithmica44, 305–321 (1995). · Zbl 0833.68096 · doi:10.1007/BF01294129 [10] Klein, P., Tarjan, R. E.: A randomized linear-time algorithm for finding minimum spanning trees. Proc. 26th Annual Symposium on Theory of Computing, pp. 9–15 (1994). [11] Pferschy, U., Rudolf, R., Woeginger, G. J.: Monge matrices make maximization manageable. Oper. Res. Lett.16, 245–254 (1994). · Zbl 0822.90112 · doi:10.1016/0167-6377(94)90037-X [12] Prim, R. C.: Shortest connection networks and some generalizations. Bell System Tech. J.36, 1389–1401 (1957). [13] Supnick, F.: Extreme Hamiltonian lines. Ann. Math.66, 179–201 (1957). · Zbl 0078.16502 · doi:10.2307/1970124 [14] Wilber, R.: The concave least-weight subsequence problem revisited. J. Algorithms9, 418–425 (1988). · Zbl 0651.68093 · doi:10.1016/0196-6774(88)90032-6