Standard

On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights. / Gimadi, Eduard Kh; Shevyakov, Aleksandr S.; Shtepa, Aleksandr A.

Recent Trends in Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. ред. / Evgeny Burnaev; Sergei Ivanov; Alexander Panchenko; Dmitry I. Ignatov; Sergei O. Kuznetsov; Michael Khachay; Olessia Koltsova; Andrei Kutuzov; Natalia Loukachevitch; Amedeo Napoli; Panos M. Pardalos; Jari Saramäki; Andrey V. Savchenko; Evgenii Tsymbalov; Elena Tutubalina. Springer Science and Business Media Deutschland GmbH, 2022. стр. 195-206 (Communications in Computer and Information Science; Том 1573 CCIS).

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

Harvard

Gimadi, EK, Shevyakov, AS & Shtepa, AA 2022, On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights. в E Burnaev, S Ivanov, A Panchenko, DI Ignatov, SO Kuznetsov, M Khachay, O Koltsova, A Kutuzov, N Loukachevitch, A Napoli, PM Pardalos, J Saramäki, AV Savchenko, E Tsymbalov & E Tutubalina (ред.), Recent Trends in Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. Communications in Computer and Information Science, Том. 1573 CCIS, Springer Science and Business Media Deutschland GmbH, стр. 195-206, 10th International Conference on Analysis of Images, Social Networks, and Texts, AIST 2021, Virtual, Online, 16.12.2021. https://doi.org/10.1007/978-3-031-15168-2_16

APA

Gimadi, E. K., Shevyakov, A. S., & Shtepa, A. A. (2022). On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights. в E. Burnaev, S. Ivanov, A. Panchenko, D. I. Ignatov, S. O. Kuznetsov, M. Khachay, O. Koltsova, A. Kutuzov, N. Loukachevitch, A. Napoli, P. M. Pardalos, J. Saramäki, A. V. Savchenko, E. Tsymbalov, & E. Tutubalina (Ред.), Recent Trends in Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers (стр. 195-206). (Communications in Computer and Information Science; Том 1573 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-15168-2_16

Vancouver

Gimadi EK, Shevyakov AS, Shtepa AA. On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights. в Burnaev E, Ivanov S, Panchenko A, Ignatov DI, Kuznetsov SO, Khachay M, Koltsova O, Kutuzov A, Loukachevitch N, Napoli A, Pardalos PM, Saramäki J, Savchenko AV, Tsymbalov E, Tutubalina E, Редакторы, Recent Trends in Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2022. стр. 195-206. (Communications in Computer and Information Science). doi: 10.1007/978-3-031-15168-2_16

Author

Gimadi, Eduard Kh ; Shevyakov, Aleksandr S. ; Shtepa, Aleksandr A. / On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights. Recent Trends in Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers. Редактор / Evgeny Burnaev ; Sergei Ivanov ; Alexander Panchenko ; Dmitry I. Ignatov ; Sergei O. Kuznetsov ; Michael Khachay ; Olessia Koltsova ; Andrei Kutuzov ; Natalia Loukachevitch ; Amedeo Napoli ; Panos M. Pardalos ; Jari Saramäki ; Andrey V. Savchenko ; Evgenii Tsymbalov ; Elena Tutubalina. Springer Science and Business Media Deutschland GmbH, 2022. стр. 195-206 (Communications in Computer and Information Science).

BibTeX

@inproceedings{82899143d7d34fe0afdde945550e02be,
title = "On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights",
abstract = "In this work we consider the m-d-UMST problem. The m-d-UMST is to find m edge-disjoint spanning trees with the given diameter d of a minimal weight in given n-vertex weighted Undirected graph G= (V, E). We give an O(n2) -time approximation algorithm solving this problem. Then we prove its asymptotic optimality in the case of complete undirected graphs. We also assume that weights of graph edges are independent random variables identically distributed from the class of biased exponential distribution.",
keywords = "Asymptotic optimality, Biased exponential distribution, Given-diameter minimal spanning tree, Probabilistic analysis",
author = "Gimadi, {Eduard Kh} and Shevyakov, {Aleksandr S.} and Shtepa, {Aleksandr A.}",
note = "Funding Information: Supported by the program of fundamental scientific researches of the SB RAS, project No. 0314-2019-0014, and by the Russian Foundation for Basic Research, project No. 20-31-90091. Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 10th International Conference on Analysis of Images, Social Networks, and Texts, AIST 2021 ; Conference date: 16-12-2021 Through 18-12-2021",
year = "2022",
doi = "10.1007/978-3-031-15168-2_16",
language = "English",
isbn = "9783031151675",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "195--206",
editor = "Evgeny Burnaev and Sergei Ivanov and Alexander Panchenko and Ignatov, {Dmitry I.} and Kuznetsov, {Sergei O.} and Michael Khachay and Olessia Koltsova and Andrei Kutuzov and Natalia Loukachevitch and Amedeo Napoli and Pardalos, {Panos M.} and Jari Saram{\"a}ki and Savchenko, {Andrey V.} and Evgenii Tsymbalov and Elena Tutubalina",
booktitle = "Recent Trends in Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights

AU - Gimadi, Eduard Kh

AU - Shevyakov, Aleksandr S.

AU - Shtepa, Aleksandr A.

N1 - Funding Information: Supported by the program of fundamental scientific researches of the SB RAS, project No. 0314-2019-0014, and by the Russian Foundation for Basic Research, project No. 20-31-90091. Publisher Copyright: © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - In this work we consider the m-d-UMST problem. The m-d-UMST is to find m edge-disjoint spanning trees with the given diameter d of a minimal weight in given n-vertex weighted Undirected graph G= (V, E). We give an O(n2) -time approximation algorithm solving this problem. Then we prove its asymptotic optimality in the case of complete undirected graphs. We also assume that weights of graph edges are independent random variables identically distributed from the class of biased exponential distribution.

AB - In this work we consider the m-d-UMST problem. The m-d-UMST is to find m edge-disjoint spanning trees with the given diameter d of a minimal weight in given n-vertex weighted Undirected graph G= (V, E). We give an O(n2) -time approximation algorithm solving this problem. Then we prove its asymptotic optimality in the case of complete undirected graphs. We also assume that weights of graph edges are independent random variables identically distributed from the class of biased exponential distribution.

KW - Asymptotic optimality

KW - Biased exponential distribution

KW - Given-diameter minimal spanning tree

KW - Probabilistic analysis

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

UR - https://www.mendeley.com/catalogue/ec8d89b2-55cf-3886-8247-8c8a226ba532/

U2 - 10.1007/978-3-031-15168-2_16

DO - 10.1007/978-3-031-15168-2_16

M3 - Conference contribution

AN - SCOPUS:85137997447

SN - 9783031151675

T3 - Communications in Computer and Information Science

SP - 195

EP - 206

BT - Recent Trends in Analysis of Images, Social Networks and Texts - 10th International Conference, AIST 2021, Revised Selected Papers

A2 - Burnaev, Evgeny

A2 - Ivanov, Sergei

A2 - Panchenko, Alexander

A2 - Ignatov, Dmitry I.

A2 - Kuznetsov, Sergei O.

A2 - Khachay, Michael

A2 - Koltsova, Olessia

A2 - Kutuzov, Andrei

A2 - Loukachevitch, Natalia

A2 - Napoli, Amedeo

A2 - Pardalos, Panos M.

A2 - Saramäki, Jari

A2 - Savchenko, Andrey V.

A2 - Tsymbalov, Evgenii

A2 - Tutubalina, Elena

PB - Springer Science and Business Media Deutschland GmbH

T2 - 10th International Conference on Analysis of Images, Social Networks, and Texts, AIST 2021

Y2 - 16 December 2021 through 18 December 2021

ER -

ID: 38057715