On bounded diameter MST problem on random instances

Standard

On bounded diameter MST problem on random instances. / Gimadi, Edward Kh; Istomin, Alexey M.; Shin, Ekaterina Yu.

In: CEUR Workshop Proceedings, Vol. 2098, 01.01.2018, p. 159-168.

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

Harvard

Gimadi, EK, Istomin, AM & Shin, EY 2018, 'On bounded diameter MST problem on random instances', CEUR Workshop Proceedings, vol. 2098, pp. 159-168.

APA

Gimadi, E. K., Istomin, A. M., & Shin, E. Y. (2018). On bounded diameter MST problem on random instances. CEUR Workshop Proceedings, 2098, 159-168.

Vancouver

Gimadi EK, Istomin AM, Shin EY. On bounded diameter MST problem on random instances. CEUR Workshop Proceedings. 2018 Jan 1;2098:159-168.

Author

Gimadi, Edward Kh ; Istomin, Alexey M. ; Shin, Ekaterina Yu. / On bounded diameter MST problem on random instances. In: CEUR Workshop Proceedings. 2018 ; Vol. 2098. pp. 159-168.

BibTeX

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

publisher = "CEUR-WS",

}

RIS

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 -

ID: 13755118