SPANNING-TREES AND SHORTEST PATHS IN MONGE GRAPHS

Authors
DUDAS T RUDOLF R
Citation
T. Dudas et R. Rudolf, SPANNING-TREES AND SHORTEST PATHS IN MONGE GRAPHS, Computing, 60(2), 1998, pp. 109-119
Citations number
14
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Computing → ACNP
ISSN journal
0010485X
Volume
60
Issue
2
Year of publication
1998
Pages
109 - 119
Database
ISI
SICI code
0010-485X(1998)60:2<109:SASPIM>2.0.ZU;2-U
Abstract
We investigate three problems on Monge graphs, i.e. complete, undirect ed weighted graphs whose distance matrix is a Monge matrix: (A) the mi nimum spanning tree problem, (B) the problem of computing all-pairs sh ortest paths and (C) the problem of determining a minimum weighted 1-t o-all shortest path tree. For all three problems best possible algorit hms (in terms of complexity) are presented.