On finding most uniform spanning trees

Zvi Galil; Baruch Schieber

doi:10.1016/0166-218X(88)90062-5

On finding most uniform spanning trees

Zvi Galil
, Baruch Schieber

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

28 Scopus citations

Abstract

We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al. [1] for the same problem.

Original language	English (US)
Pages (from-to)	173-175
Number of pages	3
Journal	Discrete Applied Mathematics
Volume	20
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(88)90062-5
State	Published - Jun 1988
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/0166-218X(88)90062-5

Cite this

@article{30505208b95949a8b522daee1316519e,

title = "On finding most uniform spanning trees",

abstract = "We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al. [1] for the same problem.",

author = "Zvi Galil and Baruch Schieber",

year = "1988",

month = jun,

doi = "10.1016/0166-218X(88)90062-5",

language = "English (US)",

volume = "20",

pages = "173--175",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - On finding most uniform spanning trees

AU - Galil, Zvi

AU - Schieber, Baruch

PY - 1988/6

Y1 - 1988/6

N2 - We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al. [1] for the same problem.

AB - We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al. [1] for the same problem.

UR - https://www.scopus.com/pages/publications/0024034526

UR - https://www.scopus.com/pages/publications/0024034526#tab=citedBy

U2 - 10.1016/0166-218X(88)90062-5

DO - 10.1016/0166-218X(88)90062-5

M3 - Article

AN - SCOPUS:0024034526

SN - 0166-218X

VL - 20

SP - 173

EP - 175

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

On finding most uniform spanning trees

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this