On Given Diameter MST Problem on Random Input Data › Обзор исследований

Standard

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).

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

Harvard

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

APA

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

Vancouver

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). doi: 10.1007/978-3-030-33394-2_3

Author

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).

BibTeX

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

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

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

}

RIS

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 -

ID: 23003627