Abstract
An O(m)-algorithm for computing the average distance of an interval graph with m edges of unit length is presented. A slight modification of the algorithm can be used for computing the average distance of a tree with weighted edges in time O(n), where n is the number of vertices.
| Original language | English |
|---|---|
| Pages (from-to) | 311-314 |
| Number of pages | 4 |
| Journal | Information Processing Letters |
| Volume | 48 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 20 Dec 1993 |
| Externally published | Yes |
Keywords
- Algorithms
- Average distance
- Graph algorithms
- Interval graphs
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications