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

Access to Document

Link to publication in Scopus

Fingerprint Dive into the research topics of 'On bounded diameter MST problem on random instances'. Together they form a unique fingerprint.

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

year = "2018",

month = jan,

day = "1",

language = "English",

volume = "2098",

pages = "159--168",

journal = "CEUR Workshop Proceedings",

issn = "1613-0073",

note = "2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 ; Conference date: 08-07-2018 Through 14-07-2018",

}

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 -