Standard

Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data. / Gimadi, Edward; Shevyakov, Alexandr; Shin, Ekaterina.

2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 48-52 8880223 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Gimadi, E, Shevyakov, A & Shin, E 2019, Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data. in 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019., 8880223, 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Institute of Electrical and Electronics Engineers Inc., pp. 48-52, 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019, Novosibirsk, Russian Federation, 26.08.2019. https://doi.org/10.1109/OPCS.2019.8880223

APA

Gimadi, E., Shevyakov, A., & Shin, E. (2019). Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data. In 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 (pp. 48-52). [8880223] (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/OPCS.2019.8880223

Vancouver

Gimadi E, Shevyakov A, Shin E. Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data. In 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 48-52. 8880223. (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019). doi: 10.1109/OPCS.2019.8880223

Author

Gimadi, Edward ; Shevyakov, Alexandr ; Shin, Ekaterina. / Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data. 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 48-52 (2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019).

BibTeX

@inproceedings{3a85b01ad0ee47d9bbe1679d62b6d5b3,
title = "Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data",
abstract = "We give an approximation deterministic algorithm for solving the Random Undirected MST with given diameter on n-vertex complete undirected 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 approach, minimum spanning tree, performance guarantees, probabilistic analysis, random inputs, undirected graph, uniform",
author = "Edward Gimadi and Alexandr Shevyakov and Ekaterina Shin",
note = "Funding Information: Supported by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014), by RFBR (project 20-01-00583), and by the Ministry of Science and Higher Education of the Russian Federation under the 5-100 Excellence Programme.; 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019 ; Conference date: 26-08-2019 Through 30-08-2019",
year = "2019",
month = aug,
doi = "10.1109/OPCS.2019.8880223",
language = "English",
series = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "48--52",
booktitle = "2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019",
address = "United States",

}

RIS

TY - GEN

T1 - Asymptotically Optimal Approach to a Given Diameter Undirected MST Problem on Random Input Data

AU - Gimadi, Edward

AU - Shevyakov, Alexandr

AU - Shin, Ekaterina

N1 - Funding Information: Supported by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014), by RFBR (project 20-01-00583), and by the Ministry of Science and Higher Education of the Russian Federation under the 5-100 Excellence Programme.

PY - 2019/8

Y1 - 2019/8

N2 - We give an approximation deterministic algorithm for solving the Random Undirected MST with given diameter on n-vertex complete undirected 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 Undirected MST with given diameter on n-vertex complete undirected 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 approach

KW - minimum spanning tree

KW - performance guarantees

KW - probabilistic analysis

KW - random inputs

KW - undirected graph

KW - uniform

UR - http://www.scopus.com/inward/record.url?scp=85078045958&partnerID=8YFLogxK

U2 - 10.1109/OPCS.2019.8880223

DO - 10.1109/OPCS.2019.8880223

M3 - Conference contribution

AN - SCOPUS:85078045958

T3 - 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

SP - 48

EP - 52

BT - 2019 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 15th International Asian School-Seminar Optimization Problems of Complex Systems, OPCS 2019

Y2 - 26 August 2019 through 30 August 2019

ER -

ID: 26009465