азбиение ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4
https://doi.org/10.29235/1561-2430-2022-58-2-155-168
Анатацыя
Изучается вычислительная сложность задачи разбиения ребер двудольного графа на наименьшее число подграфов, изоморфных подграфам простого цикла порядка 4, в специальных классах графов. Задача относится к числу NP-трудных и находит применение при организации распределения сетевых пакетов по каналам связи в процессе передачи от одного маршрутизатора к другому. Разработан алгоритм, решающий задачу в классе деревьев порядка n за время O(n log n). Выделены трудноразрешимые случаи задачи.
Аб аўтарах
О. Дугинов
Belarusian State University
Беларусь
Беларусь
С. Химич
Белорусский государственный университет
Беларусь
Беларусь
Спіс літаратуры
1. Лекции по теории графов / В. А. Емеличев [и др.]. – М.: УРСС, 2019. – 390 с.
2. Hochbaum, D. S. Covering the edges of bipartite graphs using K2,2 graphs / D. S. Hochbaum, A. Levin // Theor. Comput. Sci. – 2010. – Vol. 411. – P. 1–9.
3. Dor, D. Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture / D. Dor, M. Tarsi // SIAM J. Comput. – 1997. – Vol. 26, № 4. – P. 1166–1187. https://doi.org/10.1137/s0097539792229507
4. Holyer, I. The NP-completeness of some edge partition problems / I. Holyer // SIAM SIAM J. Comput. – 1981. – Vol. 10, № 4. – P. 713–717. https://doi.org/10.1137/0210054
5. Dyer, M. E. On the complexity of partitioning graphs into connected subgraphs / M. E. Dyer, A. M. Frieze // Discrete Appl. Math. – 1985. – Vol. 10, № 2. – P. 139–153. https://doi.org/10.1016/0166-218x(85)90008-3
6. Golumbic, M. C. Perfect elimination and chordal bipartite graphs / M. C. Golumbic, G. F. Goss // J. Graph Theory. – 1978. – Vol. 2, № 2. – P. 155–163. https://doi.org/10.1002/jgt.3190020209
7. Goh, L. Recognition of perfect elimination bipartite graphs / L. Goh, D. Rotem // Inf. Process. Lett. – 1982. – Vol. 15, № 4. – P. 179–182. https://doi.org/10.1016/0020-0190(82)90101-6
##reviewer.review.form##
Праглядаў: 612
Паслаць артыкул па эл. пошце 