Standard

On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights. / Gimadi, Edward Kh; Shevyakov, Aleksandr S.; Shtepa, Alexandr A.

Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings. ed. / Panos Pardalos; Michael Khachay; Alexander Kazakov. Springer Science and Business Media Deutschland GmbH, 2021. p. 67-78 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12755 LNCS).

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

Harvard

Gimadi, EK, Shevyakov, AS & Shtepa, AA 2021, On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights. in P Pardalos, M Khachay & A Kazakov (eds), Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12755 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 67-78, 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021, Irkutsk, Russian Federation, 05.07.2021. https://doi.org/10.1007/978-3-030-77876-7_5

APA

Gimadi, E. K., Shevyakov, A. S., & Shtepa, A. A. (2021). On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights. In P. Pardalos, M. Khachay, & A. Kazakov (Eds.), Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings (pp. 67-78). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12755 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-77876-7_5

Vancouver

Gimadi EK, Shevyakov AS, Shtepa AA. On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights. In Pardalos P, Khachay M, Kazakov A, editors, Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 67-78. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-77876-7_5

Author

Gimadi, Edward Kh ; Shevyakov, Aleksandr S. ; Shtepa, Alexandr A. / On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights. Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings. editor / Panos Pardalos ; Michael Khachay ; Alexander Kazakov. Springer Science and Business Media Deutschland GmbH, 2021. pp. 67-78 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{48f8b9f3366d442f9ae109e4c58c1128,
title = "On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights",
abstract = "We consider the intractable problem of finding several edge-disjoint spanning trees of a given diameter in an graph with random edge weights. Earlier, we have implemented an asymptotically optimal approach for this problem in the case of directed graphs. The direct use of this result for the case of undirected graphs turned out to be impossible due to the issues associated with the summation of dependent random variables. In this work we give an O(n2) -time algorithm with conditions of asymptotic optimality for the case of undirected graphs.",
keywords = "Approximation algorithm, Asymptotic optimality, Given-diameter Minimum Spanning Tree, Probabilistic analysis",
author = "Gimadi, {Edward Kh} and Shevyakov, {Aleksandr S.} and Shtepa, {Alexandr A.}",
note = "Funding Information: Supported by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014), and by the Ministry of Science and Higher Education Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021 ; Conference date: 05-07-2021 Through 10-07-2021",
year = "2021",
doi = "10.1007/978-3-030-77876-7_5",
language = "English",
isbn = "9783030778750",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "67--78",
editor = "Panos Pardalos and Michael Khachay and Alexander Kazakov",
booktitle = "Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights

AU - Gimadi, Edward Kh

AU - Shevyakov, Aleksandr S.

AU - Shtepa, Alexandr A.

N1 - Funding Information: Supported by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014), and by the Ministry of Science and Higher Education Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - We consider the intractable problem of finding several edge-disjoint spanning trees of a given diameter in an graph with random edge weights. Earlier, we have implemented an asymptotically optimal approach for this problem in the case of directed graphs. The direct use of this result for the case of undirected graphs turned out to be impossible due to the issues associated with the summation of dependent random variables. In this work we give an O(n2) -time algorithm with conditions of asymptotic optimality for the case of undirected graphs.

AB - We consider the intractable problem of finding several edge-disjoint spanning trees of a given diameter in an graph with random edge weights. Earlier, we have implemented an asymptotically optimal approach for this problem in the case of directed graphs. The direct use of this result for the case of undirected graphs turned out to be impossible due to the issues associated with the summation of dependent random variables. In this work we give an O(n2) -time algorithm with conditions of asymptotic optimality for the case of undirected graphs.

KW - Approximation algorithm

KW - Asymptotic optimality

KW - Given-diameter Minimum Spanning Tree

KW - Probabilistic analysis

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

U2 - 10.1007/978-3-030-77876-7_5

DO - 10.1007/978-3-030-77876-7_5

M3 - Conference contribution

AN - SCOPUS:85111403890

SN - 9783030778750

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 67

EP - 78

BT - Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings

A2 - Pardalos, Panos

A2 - Khachay, Michael

A2 - Kazakov, Alexander

PB - Springer Science and Business Media Deutschland GmbH

T2 - 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021

Y2 - 5 July 2021 through 10 July 2021

ER -

ID: 34128399