Edward Kh. Gimadi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Edward Kh. Gimadi has a total of 65 co-authors. Here are the top co-authors by number of shared publications:
- Oxana Yu. Tsidulko
Sobolev Institute of Mathematics
12 shared publications - Aleksandr A. Shtepa
Novosibirsk State University
10 shared publications - I. A. Rykov
Sobolev Institute of Mathematics
5 shared publications A. E. Baburin
Sobolev Institute of Mathematics
4 shared publications- Artem V. Pyatkin
Sobolev Institute of Mathematics, Novosibirsk, Russia
4 shared publications - Evgenii N. Goncharov
Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
4 shared publications
Latest Publications
- Open Access
- 27 December 2025
- Published by Ural Federal University in Ural mathematical journal
- Vol. 11 (2) , 100-118
EDGE-DISJOINT SPANNING TREES OF ARBITRARY BOUNDED DIAMETER ON RANDOM INPUTS
We consider the following NP-hard generalization of the Minimum Spanning Tree problem. Given an undirected \(n\)-vertex edge-weighted complete graph and integers \(d\) and \(m\), find \(m\) edge-disjoint spanning trees of diameter at most \(d\) with minimum total weight. We propose a new polynomial-time approximation algorithm for the problem and study its performance guarantees on random inputs, that is, when the edge weights of the graph are i. i. d. random variables. We show that under mild conditions on the distribution parameters the proposed algorithm is asymptotically optimal for the case of continuous and discrete uniform distribution on \([a_n, b_n]\), \(a_n>0\), the shifted exponential distribution with shift \(a_n>0\), and distributions dominating the above. In contrast to a number of previous results for related problems, the new algorithm is asymptotically optimal not only if \(d\) tends to infinity with \(n\), but for constant \(d\) as well.- 27 December 2025
- Published by Ural Federal University in Ural mathematical journal
- Vol. 11 (2) , 100-118
Open AccessEDGE-DISJOINT SPANNING TREES OF ARBITRARY BOUNDED DIAMETER ON RANDOM INPUTS
We consider the following NP-hard generalization of the Minimum Spanning Tree problem. Given an undirected \(n\)-vertex edge-weighted complete graph and integers \(d\) and \(m\), find \(m\) edge-disjoint spanning trees of diameter at most \(d\) with minimum total weight. We propose a new polynomial-time approximation algorithm for the problem and study its performance guarantees on random inputs, that is, when the edge weights of the graph are i. i. d. random variables. We show that under mild conditions on the distribution parameters the proposed algorithm is asymptotically optimal for the case of continuous and discrete uniform distribution on \([a_n, b_n]\), \(a_n>0\), the shifted exponential distribution with shift \(a_n>0\), and distributions dominating the above. In contrast to a number of previous results for related problems, the new algorithm is asymptotically optimal not only if \(d\) tends to infinity with \(n\), but for constant \(d\) as well. - 1 September 2025
- Published by Krasovskii Institute of Mathematics and Mechanics UB RAS in Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Vol. 31 (3)
Прямо-двойственный полиномиальный приближенный алгоритм для задачи размещения предприятий
УДК 519.8+518.25 MSC: 05C09, 05C12, 05C92 DOI: 10.21538/0134-4889-2025-31-3-77-90 Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019). В данной работе рассматривается задача размещения предприятий без ограничения на объемы производства. Эта задача является NP-трудной в сильном смысле. Для ее решения предлагается прямо-двойственный
- 1 September 2025
- Published by Krasovskii Institute of Mathematics and Mechanics UB RAS in Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Vol. 31 (3)
Прямо-двойственный полиномиальный приближенный алгоритм для задачи размещения предприятий
УДК 519.8+518.25 MSC: 05C09, 05C12, 05C92 DOI: 10.21538/0134-4889-2025-31-3-77-90 Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019). В данной работе рассматривается задача размещения предприятий без ограничения на объемы производства. Эта задача является NP-трудной в сильном смысле. Для ее решения предлагается прямо-двойственный
- 15 April 2025
- Published by Springer Nature
- p. 249-261
An Asymptotically Optimal Algorithm for the Minimum Weight Spanning Tree with Arbitrarily Bounded Diameter on Random Inputs
- 15 April 2025
- Published by Springer Nature
- p. 249-261
An Asymptotically Optimal Algorithm for the Minimum Weight Spanning Tree with Arbitrarily Bounded Diameter on Random Inputs
- 12 March 2024
- Published by Springer Nature
- p. 341-348
The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph
- 12 March 2024
- Published by Springer Nature
- p. 341-348
The Problem of Finding Several Given Diameter Spanning Trees of Maximum Total Weight in a Complete Graph
- 14 December 2023
- Published by Springer Nature
- p. 281-292
Several Edge-Disjoint Spanning Trees with Given Diameter in a Graph with Random Discrete Edge Weights
- 14 December 2023
- Published by Springer Nature
- p. 281-292
Several Edge-Disjoint Spanning Trees with Given Diameter in a Graph with Random Discrete Edge Weights
- 15 July 2023
- Published by The Russian Academy of Sciences in Автоматика и телемеханика
- No. 7,p. 146-166
On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter
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(n2), 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.
- 15 July 2023
- Published by The Russian Academy of Sciences in Автоматика и телемеханика
- No. 7,p. 146-166
On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter
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(n2), 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.
- 1 July 2023
- Published by Pleiades Publishing Ltd in Automation and Remote Control
- Vol. 84 (7) , 772-787
On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter
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}\)(n2), 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.- 1 July 2023
- Published by Pleiades Publishing Ltd in Automation and Remote Control
- Vol. 84 (7) , 772-787
On Asymptotically Optimal Approach for Finding of the Minimum Total Weight of Edge-Disjoint Spanning Trees with a Given Diameter
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}\)(n2), 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.- 2 November 2022
- Published by Springer Nature
- p. 303-314
How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs
- 2 November 2022
- Published by Springer Nature
- p. 303-314
How Fast Can the Uniform Capacitated Facility Location Problem Be Solved on Path Graphs
- 30 August 2022
- Published by Springer Nature
- p. 195-206
On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights
- 30 August 2022
- Published by Springer Nature
- p. 195-206
On Several Edge-Disjoint MSTs with Given Diameter in Undirected Graph with Exponentially Distributed Edge Weights
- 1 June 2022
- Published by Krasovskii Institute of Mathematics and Mechanics UB RAS in Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Vol. 28 (2) , 24-44
Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида
УДК 519.8 MSC: 90-02, 90B80 DOI: 10.21538/0134-4889-2022-28-2-24-44 Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019) и при финансовой поддержке РФФИ (проект 20-31-90091). В данной работе рассматриваются сетевая задача размещения с ограничениями на объемы производства предприятий (CFLP) и ее однородный вариант (UCFLP), в котором объемы
- 1 June 2022
- Published by Krasovskii Institute of Mathematics and Mechanics UB RAS in Trudy Instituta Matematiki i Mekhaniki UrO RAN
- Vol. 28 (2) , 24-44
Задача размещения с ограничениями на объемы производства предприятий на графах древесного вида
УДК 519.8 MSC: 90-02, 90B80 DOI: 10.21538/0134-4889-2022-28-2-24-44 Работа выполнена в рамках государственного задания ИМ СО РАН (проект FWNF-2022-0019) и при финансовой поддержке РФФИ (проект 20-31-90091). В данной работе рассматриваются сетевая задача размещения с ограничениями на объемы производства предприятий (CFLP) и ее однородный вариант (UCFLP), в котором объемы