zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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 \times n$ matrix $(c_{ij})_{n\times n}$ such that $c_{ij}+c_{kl} \leq c_{il} +c_{kj}$ for all $1\leq i< k\leq n$, $1\leq j< l\leq n$, $i\neq j$, $k\neq l$, $i\neq l$, $k\neq 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.
Reviewer: Xueliang Li (MR 99a:90217)

90C35Programming involving graphs or networks
90C27Combinatorial optimization
05C12Distance in graphs
05C38Paths; cycles
Full Text: DOI
[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). · Zbl 0718.90027
[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