Oleg Duginov

@bsuir.by

Department of Informatics
Belarusian State University of Informatics and Radioelectronics

Oleg Duginov


               Download Compact PDF  
https://researchid.co/duginov

EDUCATION

Belarussian State University

RESEARCH, TEACHING, or OTHER INTERESTS

Discrete Mathematics and Combinatorics, Computer Science
10

Scopus Publications

40

Scholar Citations

3

Scholar h-index

2

Scholar i10-index

Scopus Publications

  • Partitioning vertices of graphs into paths of the same length
    Oleg Duginov, Dmitriy Malyshev, Dmitriy Mokeev
    Discrete Applied Mathematics, 2025
  • A Complete Complexity Dichotomy of the Edge-Coloring Problem for All Sets of -Edge Forbidden Subgraphs
    D. S. Malyshev, O. I. Duginov
    Journal of Applied and Industrial Mathematics, 2023
    Abstract For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain a similar result for all sets of 8-edge prohibitions.
  • Some Cases of Polynomial Solvability of the Edge Coloring Problem That Are Generated by Forbidden 8-Edge Subcubic Forests
    D. S. Malyshev, O. I. Duginov
    Journal of Applied and Industrial Mathematics, 2022
    The edge-coloring problem is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges receive distinct colors. The complexity status of this problem is known for all the classes defined by the sets of forbidden subgraphs with 7 edges each. In this paper, we consider the case of prohibitions with 8 edges. It can readily be seen that the edge-coloring problem is NP-complete for such a class if there are no subcubic forests among its 8-edge prohibitions. We prove that forbidding any subcubic 8-edge forest generates a class with polynomial-time solvability of the edge-coloring problem, except for the cases formed by the disjoint sum of one of four forests and an empty graph. For all the remaining cases, we prove a similar result for the intersection with the set of graphs with a maximum degree of at least four.
  • PARTITIONING THE EDGE SET OF A BIPARTITE GRAPH INTO THE MINIMAL NUMBER OF SUBGRAPHS ISOMORPHIC TO THOSE OF A SIMPLE 4 ORDER CYCLE
    O. I. Duginov, S. S. Khimich
    Proceedings of the National Academy of Sciences of Belarus Physics and Mathematics Series, 2022
    In this paper, we study the computational complexity for a problem of partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple cycle of order 4 in special graph classes. This problem is NP-hard and finds application in organizing the distribution of network packets over communication channels in the process of transmission from one router to another. We develop anO(nlogn) algorithm for solving that problem in a class of n order trees. Intractable cases of the problem are identified.
  • STRUCTURAL AND ALGORITHMIC PROPERTIES OF MAXIMAL DISSOCIATING SETS IN GRAPHS
    О. И. Дугинов, Б. М. Кускова, Д. С. Малышев, Н. А. Шур
    Trudy Instituta Matematiki I Mekhaniki Uro Ran, 2022
    УДК 519.1 MSC: 05C70 DOI: 10.21538/0134-4889-2022-28-2-114-142 Работа выполнена Д.С. Малышевым при поддержке РФФИ (проект № 20-51-04001), О.И. Дугиновым и Н.А. Шур — при поддержке БРФФИ (проект № Ф21РМ-001). Подмножество вершин графа называется диссоциирующим, если степени вершин подграфа, порожденного этим подмножеством, не превосходят 1. Диссоциирующее множество максимально,
  • Weighted Perfect Matching with Constraints on the Total Weight of Its Parts
    O. I. Duginov
    Journal of Applied and Industrial Mathematics, 2021
    Under consideration is the following strongly NP-hard problem: Given a balanced complete bipartite graph with weights on the edges and a partition of one of its parts into nonempty and pairwise disjoint subsets, find a perfect matching of this graph such that the maximum total weight of edges of the matching incident to vertices of one subset of the partition is minimal. We propose some characterization of solutions for a special case of this problem in which, firstly, the weights of graph edges take values in $$\{0, 1, \Delta \}$$ , where $$\Delta $$ is an integer greater than the number of edges of the unit weight; and, secondly, there is a perfect matching of the graph that consists of the edges only with weights $$0 $$ and $$1 $$ . Moreover, we identify the cases of problems that are polynomially solvable and strongly NP-hard. Finally, we show that if the number of subsets forming the partition of the special part of the graph is fixed then the problem is equivalent to finding a perfect matching of a given weight in an edge-weighted bipartite graph.
  • Bottleneck subset-type restricted matching problems
    Oleg Duginov
    Journal of Combinatorial Optimization, 2020
  • PARTITIONING A SPLIT GRAPH INTO INDUCED SUBGRAPHS ISOMORPHIC TO THE PATH OF ORDER 3
    O. I. Duginov
    Proceedings of the National Academy of Sciences of Belarus Physics and Mathematics Series, 2019
    The study of the computational complexity of problems on graphs is an urgent problem. We show that the problem of deciding whether the vertex set of a given split graph of order 3n can be partitioned into induced subgraphs isomorphic to P3 is a polynomially solvable problem. We develop a polynomial-time algorithm based on the method of augmenting graphs. The developed efficient algorithm can be used for solving team formation problems.
  • Secure total domination in graphs: Bounds and complexity
    Oleg Duginov
    Discrete Applied Mathematics, 2017
  • Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
    Discrete Mathematics and Theoretical Computer Science, 2014

RECENT SCHOLAR PUBLICATIONS

  • Partitioning vertices of graphs into paths of the same length
    O Duginov, D Malyshev, D Mokeev
    Discrete Applied Mathematics 373, 179-195 , 2025
    2025
  • Chordal bipartite graphs, biclique vertex partitions and Castelnuovo-Mumford regularity of -subdivision graphs
    Y Civan, Z Deniz, O Duginov, MA Yetim
    arXiv preprint arXiv:2410.15213 , 2024
    2024
    Citations: 1
  • Разбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4
    ОИ Дугинов, СС Химич
    Известия Национальной академии наук Беларуси. Серия физико-математических … , 2022
    2022
  • Structural and algorithmic properties of maximal dissociating sets in graphs
    OI Duginov, BM Kuskova, DS Malyshev, NA Shur
    Trudy Instituta Matematiki i Mekhaniki UrO RAN 28 (2), 114-142 , 2022
    2022
  • Структурные и алгоритмические свойства максимальных диссоциирующих множеств в графах
    О Дугинов, Б Кускова, Д Малышев, Н Шур
    Труды Института математики и механики УрО РАН 28 (2), 114-142 , 2022
    2022
  • Weighted Perfect Matching with Constraints on the Total Weight of Its Parts
    OI Duginov
    Journal of Applied and Industrial Mathematics 15 (3), 393-412 , 2021
    2021
    Citations: 1
  • Взвешенное совершенное паросочетание с ограничениями на суммарный вес его частей
    ОИ Дугинов
    Дискретный анализ и исследование операций 28 (3), 5-37 , 2021
    2021
    Citations: 1
  • Bottleneck subset-type restricted matching problems
    O Duginov
    Journal of Combinatorial Optimization 40 (3), 796-805 , 2020
    2020
  • Partitioning a split graph into induced subgraphs isomorphic to the path of order 3
    OI Duginov
    Proceedings of the National Academy of Sciences of Belarus. Physics and … , 2019
    2019
    Citations: 1
  • Дискретная математика и математическая логика.№ УД-5083/уч.
    ОИ Дугинов
    Минск: БГУ , 2018
    2018
  • Secure total domination in graphs: Bounds and complexity
    O Duginov
    Discrete Applied Mathematics 222, 97-108 , 2017
    2017
    Citations: 15
  • Задача минимального пополнения двудольного графа
    ОИ Дугинов, ИГ Кузнецова
    Доклады Национальной академии наук Беларуси 59 (6), 24-32 , 2016
    2016
  • On the complexity of the clustering minimum biclique completion problem
    O Duginov
    Минск: Институт математики НАН Беларуси , 2015
    2015
    Citations: 1
  • Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
    O Duginov
    Discrete Mathematics and Theoretical Computer Science 16 (3), 203-214 , 2014
    2014
    Citations: 15
  • Полиномиально разрешимые случаи задачи о наименьшем покрытии вершин графа бикликами
    ОИ Дугинов
    Доклады Национальной академии наук Беларуси 58 (2), 5-10 , 2014
    2014
  • Покрытие расщепляемого графа наименьшим числом полных двудольных подграфов
    ОИ Дугинов
    Известия Национальной академии наук Беларуси. Серия физико-математических … , 2014
    2014
  • Сложность задач покрытия графа наименьшим числом полных двудольных графов
    ОИ Дугинов
    Труды Института математики НАН Беларуси 22 (1), 51-69 , 2014
    2014
    Citations: 3
  • О бикликовом разбиении короны и соединения графов
    ВВ Лепин, ОИ Дугинов
    Доклады Национальной академии наук Беларуси 56 (3), 10-15 , 2012
    2012
    Citations: 2

MOST CITED SCHOLAR PUBLICATIONS

  • Secure total domination in graphs: Bounds and complexity
    O Duginov
    Discrete Applied Mathematics 222, 97-108 , 2017
    2017
    Citations: 15
  • Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs
    O Duginov
    Discrete Mathematics and Theoretical Computer Science 16 (3), 203-214 , 2014
    2014
    Citations: 15
  • Сложность задач покрытия графа наименьшим числом полных двудольных графов
    ОИ Дугинов
    Труды Института математики НАН Беларуси 22 (1), 51-69 , 2014
    2014
    Citations: 3
  • О бикликовом разбиении короны и соединения графов
    ВВ Лепин, ОИ Дугинов
    Доклады Национальной академии наук Беларуси 56 (3), 10-15 , 2012
    2012
    Citations: 2
  • Chordal bipartite graphs, biclique vertex partitions and Castelnuovo-Mumford regularity of -subdivision graphs
    Y Civan, Z Deniz, O Duginov, MA Yetim
    arXiv preprint arXiv:2410.15213 , 2024
    2024
    Citations: 1
  • Weighted Perfect Matching with Constraints on the Total Weight of Its Parts
    OI Duginov
    Journal of Applied and Industrial Mathematics 15 (3), 393-412 , 2021
    2021
    Citations: 1
  • Взвешенное совершенное паросочетание с ограничениями на суммарный вес его частей
    ОИ Дугинов
    Дискретный анализ и исследование операций 28 (3), 5-37 , 2021
    2021
    Citations: 1
  • Partitioning a split graph into induced subgraphs isomorphic to the path of order 3
    OI Duginov
    Proceedings of the National Academy of Sciences of Belarus. Physics and … , 2019
    2019
    Citations: 1
  • On the complexity of the clustering minimum biclique completion problem
    O Duginov
    Минск: Институт математики НАН Беларуси , 2015
    2015
    Citations: 1
  • Partitioning vertices of graphs into paths of the same length
    O Duginov, D Malyshev, D Mokeev
    Discrete Applied Mathematics 373, 179-195 , 2025
    2025
  • Разбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4
    ОИ Дугинов, СС Химич
    Известия Национальной академии наук Беларуси. Серия физико-математических … , 2022
    2022
  • Structural and algorithmic properties of maximal dissociating sets in graphs
    OI Duginov, BM Kuskova, DS Malyshev, NA Shur
    Trudy Instituta Matematiki i Mekhaniki UrO RAN 28 (2), 114-142 , 2022
    2022
  • Структурные и алгоритмические свойства максимальных диссоциирующих множеств в графах
    О Дугинов, Б Кускова, Д Малышев, Н Шур
    Труды Института математики и механики УрО РАН 28 (2), 114-142 , 2022
    2022
  • Bottleneck subset-type restricted matching problems
    O Duginov
    Journal of Combinatorial Optimization 40 (3), 796-805 , 2020
    2020
  • Дискретная математика и математическая логика.№ УД-5083/уч.
    ОИ Дугинов
    Минск: БГУ , 2018
    2018
  • Задача минимального пополнения двудольного графа
    ОИ Дугинов, ИГ Кузнецова
    Доклады Национальной академии наук Беларуси 59 (6), 24-32 , 2016
    2016
  • Полиномиально разрешимые случаи задачи о наименьшем покрытии вершин графа бикликами
    ОИ Дугинов
    Доклады Национальной академии наук Беларуси 58 (2), 5-10 , 2014
    2014
  • Покрытие расщепляемого графа наименьшим числом полных двудольных подграфов
    ОИ Дугинов
    Известия Национальной академии наук Беларуси. Серия физико-математических … , 2014
    2014