Avtomatika i Telemekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Avtomatika i Telemekhanika, 2023, Issue 7, Pages 146–166
DOI: https://doi.org/10.31857/S0005231023070085 (Mi at16118) 		 
Optimization, System Analysis, and Operations Research

On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter

E. Kh. Gimadia, A. A. Shtepab

a Sobolev Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
Full-text PDF (620 kB) First page
References:
PDF
HTML
DOI: https://doi.org/10.31857/S0005231023070085
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 $\mathcal{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: given-diameter Minimum Spanning Tree, approximation algorithm, asymptotic optimality, probabilistic analysis.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation FWNF-2022-001
The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics SB RAS (project FWNF-2022-0019).
Presented by the member of Editorial Board: A. A. Lazarev

Received: 23.01.2023
Revised: 27.03.2023
Accepted: 28.04.2023
English version:
Automation and Remote Control, 2023, Volume 84, Issue 7, Pages 872–888
DOI: https://doi.org/10.25728/arcRAS.2023.42.85.001
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: E. Kh. Gimadi, A. A. Shtepa, “On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter”, Avtomat. i Telemekh., 2023, no. 7, 146–166; Autom. Remote Control, 84:7 (2023), 872–888
Citation in format AMSBIB
\Bibitem{GimSht23}
\by E.~Kh.~Gimadi, A.~A.~Shtepa
\paper On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter
\jour Avtomat. i Telemekh.
\yr 2023
\issue 7
\pages 146--166
\mathnet{http://mi.mathnet.ru/at16118}
\crossref{https://doi.org/10.31857/S0005231023070085}
\edn{https://elibrary.ru/FDWYOE}
\transl
\jour Autom. Remote Control
\yr 2023
\vol 84
\issue 7
\pages 872--888
\crossref{https://doi.org/10.25728/arcRAS.2023.42.85.001}
Linking options:
  • https://www.mathnet.ru/eng/at16118
  • https://www.mathnet.ru/eng/at/y2023/i7/p146
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Avtomatika i Telemekhanika
    Statistics & downloads:
    Abstract page:64
    References:15
    First page:4
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024