On Given Diameter MST Problem on Random Input Data

Edward Kh Gimadi; Ekaterina Yu Shin

doi:10.1007/978-3-030-33394-2_3

On Given Diameter MST Problem on Random Input Data

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

Аннотация

We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. 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 with positive ends. Sufficient conditions of asymptotic optimality are presented.

Язык оригинала	английский
Название основной публикации	Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers
Редакторы	Igor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova
Издатель	Springer Gabler
Страницы	30-38
Число страниц	9
ISBN (печатное издание)	9783030333935
DOI	https://doi.org/10.1007/978-3-030-33394-2_3
Состояние	Опубликовано - 1 янв 2019
Событие	18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Российская Федерация Продолжительность: 8 июл 2019 → 12 июл 2019

Серия публикаций

Название	Communications in Computer and Information Science
Том	1090 CCIS
ISSN (печатное издание)	1865-0929
ISSN (электронное издание)	1865-0937

Конференция

Конференция	18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
Страна	Российская Федерация
Город	Ekaterinburg
Период	08.07.2019 → 12.07.2019

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

10.1007/978-3-030-33394-2_3

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «On Given Diameter MST Problem on Random Input Data». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

Gimadi, E. K., & Shin, E. Y. (2019). On Given Diameter MST Problem on Random Input Data. В I. Bykadorov, V. Strusevich, & T. Tchemisova (Ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers (стр. 30-38). (Communications in Computer and Information Science; Том 1090 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-33394-2_3

Gimadi, Edward Kh ; Shin, Ekaterina Yu. / On Given Diameter MST Problem on Random Input Data. Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. редактор / Igor Bykadorov ; Vitaly Strusevich ; Tatiana Tchemisova. Springer Gabler, 2019. стр. 30-38 (Communications in Computer and Information Science).

@inproceedings{6662222e38a44d099089ef1a5772ee7d,

title = "On Given Diameter MST Problem on Random Input Data",

abstract = "We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. 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 with positive ends. Sufficient conditions of asymptotic optimality are presented.",

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

author = "Gimadi, {Edward Kh} and Shin, {Ekaterina Yu}",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-33394-2_3",

language = "English",

isbn = "9783030333935",

series = "Communications in Computer and Information Science",

publisher = "Springer Gabler",

pages = "30--38",

editor = "Igor Bykadorov and Vitaly Strusevich and Tatiana Tchemisova",

booktitle = "Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers",

address = "Germany",

note = "18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

}

Gimadi, EK & Shin, EY 2019, On Given Diameter MST Problem on Random Input Data. в I Bykadorov, V Strusevich & T Tchemisova (ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. Communications in Computer and Information Science, том. 1090 CCIS, Springer Gabler, стр. 30-38, 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, Ekaterinburg, Российская Федерация, 08.07.2019. https://doi.org/10.1007/978-3-030-33394-2_3

On Given Diameter MST Problem on Random Input Data. / Gimadi, Edward Kh; Shin, Ekaterina Yu.

Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. ред. / Igor Bykadorov; Vitaly Strusevich; Tatiana Tchemisova. Springer Gabler, 2019. стр. 30-38 (Communications in Computer and Information Science; Том 1090 CCIS).

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › рецензирование

TY - GEN

T1 - On Given Diameter MST Problem on Random Input Data

AU - Gimadi, Edward Kh

AU - Shin, Ekaterina Yu

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. 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 with positive ends. Sufficient conditions of asymptotic optimality are presented.

AB - We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. 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 with positive ends. Sufficient conditions of asymptotic optimality are presented.

KW - Asymptotically optimal algorithm

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=85076188447&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-33394-2_3

DO - 10.1007/978-3-030-33394-2_3

M3 - Conference contribution

AN - SCOPUS:85076188447

SN - 9783030333935

T3 - Communications in Computer and Information Science

SP - 30

EP - 38

BT - Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers

A2 - Bykadorov, Igor

A2 - Strusevich, Vitaly

A2 - Tchemisova, Tatiana

PB - Springer Gabler

T2 - 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019

Y2 - 8 July 2019 through 12 July 2019

ER -

Gimadi EK, Shin EY. On Given Diameter MST Problem on Random Input Data. В Bykadorov I, Strusevich V, Tchemisova T, редакторы, Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers. Springer Gabler. 2019. стр. 30-38. (Communications in Computer and Information Science). https://doi.org/10.1007/978-3-030-33394-2_3