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

Результат исследования: Научные публикации в периодических изданиях › статья по материалам конференции

Аннотация

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.

Язык оригинала	английский
Страницы (с-по)	159-168
Число страниц	10
Журнал	CEUR Workshop Proceedings
Том	2098
Состояние	Опубликовано - 1 янв 2018
Событие	2018 School-Seminar on Optimization Problems and their Applications, OPTA-SCL 2018 - Omsk, Российская Федерация Продолжительность: 8 июл 2018 → 14 июл 2018

Доступ к документу

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «On bounded diameter MST problem on random instances». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

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

}

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

В: CEUR Workshop Proceedings, Том 2098, 01.01.2018, стр. 159-168.

Результат исследования: Научные публикации в периодических изданиях › статья по материалам конференции

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 -