|
|||||
|
|
A linear-time algorithm to compute a MAD tree of an interval graph |
|
| Authors: | Elias Dahlhaus R Ravi |
| Affiliation: | a Department of Computer Science, University of Bonn, Bonn, Germany b School of Mathematical and Statistical Sciences, University of Natal, Durban, South Africa c Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA, USA |
| Abstract: | The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree. |
| Keywords: | Graph algorithms Interval graphs Spanning tree |
| 本文献已被 ScienceDirect 等数据库收录！ | |