Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 1088.90539
Dudás, T.; Rudolf, R.
Spanning trees and shortest paths in Monge graphs.
(English)
[J] Computing 60, No. 2, 109-119 (1998). ISSN 0010-485X; ISSN 1436-5057/e

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.
[Xueliang Li (MR 99a:90217)]
MSC 2000:
*90C35 Network programming
90C27 Combinatorial programming
05C05 Trees
05C12 Distance in graphs
05C38 Paths and cycles

Highlights
Master Server