Standard

The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph. / Gimadi, E. Kh; Shtepa, A. A.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Science and Business Media Deutschland GmbH, 2024. p. 341-348 24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14486 LNCS).

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

Harvard

Gimadi, EK & Shtepa, AA 2024, The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)., 24, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14486 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 341-348, 11th International Conference on Analysis of Images, Social Networks and Texts, Ереван, Armenia, 28.09.2023. https://doi.org/10.1007/978-3-031-54534-4_24

APA

Gimadi, E. K., & Shtepa, A. A. (2024). The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 341-348). [24] (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14486 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-54534-4_24

Vancouver

Gimadi EK, Shtepa AA. The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Science and Business Media Deutschland GmbH. 2024. p. 341-348. 24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-54534-4_24

Author

Gimadi, E. Kh ; Shtepa, A. A. / The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Science and Business Media Deutschland GmbH, 2024. pp. 341-348 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{770f5836fdce46f5a54fb4379c61e2b4,
title = "The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph",
abstract = "We consider the following NP-hard problem. Given an undirected complete edge-weighted graph and positive integers m, D, the goal is to find m edge-disjoint spanning trees with diameter D of maximum total weight in complete undirected graph. We propose an O(n2)-time approximation algorithm for the problem, where n is the number of vertices in the input graph. For the case when edge weights are randomly uniformly chosen from the interval (0; 1), we prove sufficient conditions under which the proposed algorithm gives asymptotically optimal solutions.",
keywords = "approximation algorithm, asymptotic optimality, given diameter Spanning Tree Problem, 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 (project FWNF-2022-0019).; 11th International Conference on Analysis of Images, Social Networks and Texts, AIST 2023 ; Conference date: 28-09-2023 Through 30-09-2023",
year = "2024",
doi = "10.1007/978-3-031-54534-4_24",
language = "English",
isbn = "9783031545337",
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 = "341--348",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",

}

RIS

TY - GEN

T1 - The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph

AU - Gimadi, E. Kh

AU - Shtepa, A. A.

N1 - Conference code: 11

PY - 2024

Y1 - 2024

N2 - We consider the following NP-hard problem. Given an undirected complete edge-weighted graph and positive integers m, D, the goal is to find m edge-disjoint spanning trees with diameter D of maximum total weight in complete undirected graph. We propose an O(n2)-time approximation algorithm for the problem, where n is the number of vertices in the input graph. For the case when edge weights are randomly uniformly chosen from the interval (0; 1), we prove sufficient conditions under which the proposed algorithm gives asymptotically optimal solutions.

AB - We consider the following NP-hard problem. Given an undirected complete edge-weighted graph and positive integers m, D, the goal is to find m edge-disjoint spanning trees with diameter D of maximum total weight in complete undirected graph. We propose an O(n2)-time approximation algorithm for the problem, where n is the number of vertices in the input graph. For the case when edge weights are randomly uniformly chosen from the interval (0; 1), we prove sufficient conditions under which the proposed algorithm gives asymptotically optimal solutions.

KW - approximation algorithm

KW - asymptotic optimality

KW - given diameter Spanning Tree Problem

KW - probabilistic analysis

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

UR - https://www.mendeley.com/catalogue/f03e4fec-c7ef-385b-b5f6-8a94d3fd6d9e/

U2 - 10.1007/978-3-031-54534-4_24

DO - 10.1007/978-3-031-54534-4_24

M3 - Conference contribution

SN - 9783031545337

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

SP - 341

EP - 348

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

PB - Springer Science and Business Media Deutschland GmbH

T2 - 11th International Conference on Analysis of Images, Social Networks and Texts

Y2 - 28 September 2023 through 30 September 2023

ER -

ID: 60483607