On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter

Standard

On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter. / Gimadi, E. Kh; Shtepa, A. A.

In: Automation and Remote Control, Vol. 84, No. 7, 07.2023, p. 772-787.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{54fb8d352bbd46c89b055f2b7b03fbbd,

title = "On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter",

abstract = "We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity O(n 2), where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution.",

keywords = "approximation algorithm, asymptotic optimality, minimum spanning tree with given diameter, probabilistic analysis",

author = "Gimadi, {E. Kh} and Shtepa, {A. A.}",

note = "The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences (project FWNF-2022-0019). Публикация для корректировки.",

year = "2023",

month = jul,

doi = "10.1134/S0005117923070068",

language = "English",

volume = "84",

pages = "772--787",

journal = "Automation and Remote Control",

issn = "0005-1179",

publisher = "Maik Nauka-Interperiodica Publishing",

number = "7",

}

RIS

TY - JOUR

T1 - On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter

AU - Gimadi, E. Kh

AU - Shtepa, A. A.

N1 - The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences (project FWNF-2022-0019). Публикация для корректировки.

PY - 2023/7

Y1 - 2023/7

N2 - We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity O(n 2), where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution.

AB - We consider the intractable problem of finding several edge-disjoint spanning trees of the minimum total weight with a given diameter in complete undirected graph in current paper. The weights of edges of a graph are random variables from several continuous distributions: uniform, biased truncated exponential, biased truncated normal. The approximation algorithm with time complexity O(n 2), where n is number of vertices in graph, is proposed for solving this problem. The asymptotic optimality conditions for constructed algorithm is presented for each considered probabilistic distribution.

KW - approximation algorithm

KW - asymptotic optimality

KW - minimum spanning tree with given diameter

KW - probabilistic analysis

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85173630092&origin=inward&txGid=b09994e7f5c6b55829b295afdce57890

UR - https://www.mendeley.com/catalogue/ea088c3c-db0c-33fe-b104-e785a6bfe878/

U2 - 10.1134/S0005117923070068

DO - 10.1134/S0005117923070068

M3 - Article

VL - 84

SP - 772

EP - 787

JO - Automation and Remote Control

JF - Automation and Remote Control

SN - 0005-1179

IS - 7

ER -

ID: 59564473