Задача о ({K1, K2},k,l)-упаковке наибольшего веса в графе
https://doi.org/10.29235/1561-2430-2023-59-2-121-129
Аннотация
Рассматривается задача о ({K1,K2},k,l)-упаковке наибольшего веса в графе, которая обобщает ряд известных задач, например, о независимом множестве, максимальном индуцированном паросочетании, k-разделенном паросочетании, связном паросочетании, диссоциирующем множестве, k-упаковке. Показано, что в классе кографов ({K1,K2},k,l)-упаковку наибольшего веса можно найти за время O(n + m). Пусть Г – класс графов и Г* – класс всех простых (относительно модульной декомпозиции) порожденных подграфов из Г. Доказано, что если задача об оптимальной ({K1,K2},k,l)-упаковке графа может быть решена в классе графов Г* за время O(np ), где p ≥ 2 – константа, то эта задача может быть решена в классе графов Г за время O(np ).
Ключевые слова
граф,
упаковка,
модульная декомпозиция,
индуцированное паросочетание,
k-разделенное паросочетание,
k-упаковка
Об авторе
В. В. Лепин
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Лепин Виктор Васильевич – кандидат физико-математических наук, ученый секретарь
ул. Сурганова, 11, 220072, Минск
Список литературы
1. Yuster R. Combinatorial and computational aspects of graph packing and graph decomposition / R. Yuster // Comput. Sci. Rev. – 2007. – Vol. 1, № 1. – P. 12–26. https://doi.org/10.1016/j.cosrev.2007.07.002
2. Joos, F. Equality of distance packing numbers / F. Joos, D. Rautenbach // Discrete Math. – 2015. – Vol. 338, № 12. – P. 2374–2377. https://doi.org/10.1016/j.disc.2015.06.003
3. Brandstädt, A. On distance-3 matchings and induced matchings. / A. Brandstädt, R. Mosca // Discrete Appl. Math. – 2011. – Vol. 159, № 7, pp. 509–520. https://doi.org/10.1016/j.dam.2010.05.022
4. Computational complexity of maximum distance-(k,l) matchings in graphs / N. Brauner [et al.] // Международный конгресс по информатике: информационные системы и технологии: материалы Междунар. науч. конгресса, Минск, 31 окт. – 3 нояб. 2011 г.: в 2 ч. – Минск, 2011. – Ч. 1. – С. 341–346.
5. Kartynnik Yu., Ryzhikov A. On Minimum Maximal Distance-k Matchings / Y. Kartynnik, A. Ryzhikov // Electron. Notes Discrete Math. – 2016. – Vol. 56. – P. 71–76. https://doi.org/10.1016/j.endm.2016.11.011
6. Topp, J. On packing and covering numbers of graphs / J. Topp, L. Volkmann // Discrete Math. – 1991. – Vol. 96, № 3. – P. 229–238. https://doi.org/10.1016/0012-365x(91)90316-t
7. Meir, A. Relations between packing and covering numbers of a tree / A. Meir, J. W. Moon // Pacific J. Math. – 1975. – Vol. 61, № 1. – P. 225–233. https://doi.org/10.2140/pjm.1975.61.225
8. The complexity of dissociation set problems in graphs / Yu. Orlovich [et al.] // Discrete Appl. Math. – 2011. – Vol. 159, № 13. – P. 1352–1366. https://doi.org/10.1016/j.dam.2011.04.023
9. Gallai, T. Transitiv orienterbare graphe / T. Gallai // Acta Math. Acad. Sci. Hungar. – 1967. – Vol. 18, № 1–2. – P. 25–66. https://doi.org/10.1007/bf02020961
10. James, L. O. Graph decomposition for undirected graphs / L. O. James, R. G. Stanton, D. D. Cowan // Proc. of the Third Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, Feb. 28 – March 2, 1972. – Florida, 1972. – P. 281–290.
11. Simpler linear-time modular decomposition via recursive factorizing permutations / M. Tedder [et al.] // Int. Colloquium on Automata, Languages and Programming (ICALP 2008). – Berlin; Heidelberg: Springer, 2008. – P. 634–645. – (Lecture Notes in Computer Science, vol 5125). https://doi.org/10.1007/978-3-540-70575-8_52
Рецензия
Просмотров: 366
Послать статью по эл. почте 