Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]