Computing the average distance of an interval graph

Peter Dankelmann

doi:10.1016/0020-0190(93)90174-8

Computing the average distance of an interval graph

Peter Dankelmann

RWTH Aachen University

Research output: Contribution to journal › Article › peer-review

20 Citations (Scopus)

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	https://doi.org/10.1016/0020-0190(93)90174-8
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

Access to Document

10.1016/0020-0190(93)90174-8

Cite this

@article{e72235d829384b27a0bc5ae5664e0020,

title = "Computing the average distance of an interval graph",

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.",

keywords = "Algorithms, Average distance, Graph algorithms, Interval graphs",

author = "Peter Dankelmann",

year = "1993",

month = dec,

day = "20",

doi = "10.1016/0020-0190(93)90174-8",

language = "English",

volume = "48",

pages = "311--314",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Computing the average distance of an interval graph

AU - Dankelmann, Peter

PY - 1993/12/20

Y1 - 1993/12/20

N2 - 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.

AB - 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.

KW - Algorithms

KW - Average distance

KW - Graph algorithms

KW - Interval graphs

UR - http://www.scopus.com/inward/record.url?scp=0027814866&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(93)90174-8

DO - 10.1016/0020-0190(93)90174-8

M3 - Article

AN - SCOPUS:0027814866

SN - 0020-0190

VL - 48

SP - 311

EP - 314

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Computing the average distance of an interval graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this