On bounded diameter MST problem on random instances

Edward Kh Gimadi; Alexey M. Istomin; Ekaterina Yu Shin

On bounded diameter MST problem on random instances

Edward Kh Gimadi, Alexey M. Istomin, Ekaterina Yu Shin

Research output: Contribution to journal › Conference article › peer-review

Abstract

We give an approximation deterministic algorithm for solving the Random bounded diameter minimum spanning tree (BDMST) problem on an undirected graph. The algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval (an;b_n). Conditions of asymptotic optimality are presented.

Original language	English
Pages (from-to)	159-168
Number of pages	10
Journal	CEUR Workshop Proceedings
Volume	2098
Publication status	Published - 1 Jan 2018
Event	2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 - Omsk, Russian Federation Duration: 8 Jul 2018 → 14 Jul 2018

Keywords

Asymptotically optimal algorithm
Bounded diameter minimum spanning tree
Graph
Minimum spanning tree
Performance guarantees
Probabilistic analysis
Random inputs
Uniform

Cite this

@article{1ec9dd9199a2487c8baa96839cc22be5,

title = "On bounded diameter MST problem on random instances",

abstract = "We give an approximation deterministic algorithm for solving the Random bounded diameter minimum spanning tree (BDMST) problem on an undirected graph. The algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval (an;bn). Conditions of asymptotic optimality are presented.",

keywords = "Asymptotically optimal algorithm, Bounded diameter minimum spanning tree, Graph, Minimum spanning tree, Performance guarantees, Probabilistic analysis, Random inputs, Uniform",

author = "Gimadi, {Edward Kh} and Istomin, {Alexey M.} and Shin, {Ekaterina Yu}",

note = "Publisher Copyright: Copyright {\textcopyright} by the paper's authors.; 2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 ; Conference date: 08-07-2018 Through 14-07-2018",

year = "2018",

month = jan,

day = "1",

language = "English",

volume = "2098",

pages = "159--168",

journal = "CEUR Workshop Proceedings",

issn = "1613-0073",

}

TY - JOUR

T1 - On bounded diameter MST problem on random instances

AU - Gimadi, Edward Kh

AU - Istomin, Alexey M.

AU - Shin, Ekaterina Yu

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We give an approximation deterministic algorithm for solving the Random bounded diameter minimum spanning tree (BDMST) problem on an undirected graph. The algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval (an;bn). Conditions of asymptotic optimality are presented.

AB - We give an approximation deterministic algorithm for solving the Random bounded diameter minimum spanning tree (BDMST) problem on an undirected graph. The algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval (an;bn). Conditions of asymptotic optimality are presented.

KW - Asymptotically optimal algorithm

KW - Bounded diameter minimum spanning tree

KW - Graph

KW - Minimum spanning tree

KW - Performance guarantees

KW - Probabilistic analysis

KW - Random inputs

KW - Uniform

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

M3 - Conference article

AN - SCOPUS:85047982363

VL - 2098

SP - 159

EP - 168

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

SN - 1613-0073

T2 - 2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018

Y2 - 8 July 2018 through 14 July 2018

ER -

On bounded diameter MST problem on random instances

Abstract

Keywords

Other files and links

Fingerprint

Cite this