Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях
https://doi.org/10.18255/1818-1015-2015-4-453-463
Аннотация
Исследуются полиэдральные графы двух задач о минимальном остовном дереве при дополнительных ограничениях. В первой задаче речь идет об отыскании дерева с минимальной суммой весов ребер среди всех остовных деревьев, количество висячих вершин которых не превосходит заданную величину. Во второй задаче дополнительное ограничение заключается в предположении о том, что степени всех вершин искомого дерева не превосходят заданную величину. Обе рассматриваемые задачи в варианте распознавания являются NP-полными. В работе изучаются многогранники указанных задач и их графы. Устанавливается, что в обоих случаях распознавание смежности вершин этих графов представляет собой NP-полную задачу. Несмотря на это, удается получить сверхполиномиальные нижние оценки плотности (кликового числа) этих графов, которые характеризуют временную трудоемкость в широком классе алгоритмов, использующих линейные сравнения. Приведенные результаты свидетельствуют о принципиальном отличии комбинаторно–геометрических свойств рассматриваемых задач от классической задачи о минимальном остовном дереве.
Ключевые слова
Об авторах
В. А. Бондаренко
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
д-р физ.-мат. наук, профессор
ул. Советская, 14, г. Ярославль, 150000, Россия
А. В. Николаев
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
канд. физ.-мат. наук
ул. Советская, 14, г. Ярославль, 150000, Россия
Д. А. Шовгенов
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
аспирант
ул. Советская, 14, г. Ярославль, 150000, Россия
Список литературы
1. Бондаренко В. А., “Оценки сложности задач комбинаторной оптимизации в одном классе алгоритмов”, Доклады Академии наук, 328:1 (1993), 22–24; [Bondarenko V. A., “Complexity bounds for combinatorial optimization problems in one class of algorithms”, Russian Academy of Sciences Doklady Mathematics, 328:1 (1993), 22–24, (in Russian).]
2. Бондаренко В. А., Максименко А. Н., Геометрические конструкции и сложность в комбинаторной оптимизации, ЛКИ, М., 2008, 184 с.; [Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost' v kombinatornoy optimizatsii, LKI, Moscow, 2008, (in Russian).]
3. Бондаренко В. А., Николаев А. В., “Комбинаторно-геометрические свойства задачи о разрезе”, Доклады Академии наук, 452:2 (2013), 127–129; [Bondarenko V. A., Nikolaev A. V., “Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems”, Doklady Mathematics, 88:2 (2013), 516–517]
4. Пападимитриу Х., Стайглиц К., Комбинаторная оптимизация: алгоритмы и сложность, Мир, М., 1985, 512 с.; [Papadimitriou C. H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982.]
5. Гэри M., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.; [Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979.]
6. Rahman M. S., Kaykobad M., “Complexities of some interesting problems on spanning trees”, Information Processing Letters, 94:2 (2005), 93–97.
7. Fernandes L. M., Gouveia L., “Minimal spanning trees with a constraint on the number of leaves”, European Journal of Operational Research, 104:1 (1998), 250–261.
8. Goemans M. X., “Minimum Bounded-Degree Spanning Trees”, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, 273–282.
9. Salamon G., Wiener G., “On finding spanning trees with few leaves”, Information Processing Letters, 105:5 (2008), 164–169.
10. Singh M., Lau L. C., “Approximating minimum bounded degree spanning trees to within one of optimal”, Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing., 2007, 661–670.
11. Бренстед А., Введение в теорию выпуклых многогранников, Мир, М., 1988, 240 с.; [Brondsted A., An Introduction to Convex Polytopes, Springer-Verlag, 1983.]
12. Martin R. K., “Using separation algorithms to generate mixed integer model reformulations”, Operations Research Letters, 10:3 (1991), 119–128.
13. Белов Ю.А., “О плотности графа матроида”, Модели исследования операций в вычислительных системах, Яросл. гос. ун-т., Ярославль, 1985, 95–100; [Belov Y. A., “O plotnosti grafa matroida”, Modeli issledovanija operacij v vychislitelnyh sistemah, Yaroslavl state university, Yaroslavl, 1985, 95–100, (in Russian).]
14. Fujie T., “The maximum-leaf spanning tree problem: Formulations and facets”, Networks, 43:4 (2004), 212–223.
15. Papadimitriou C. H., “The Adjacency Relation on the Traveling Salesman Polytope is NP-Complete”, Mathematical Programming, 14:1 (1978), 312–324.
Рецензия
Для цитирования:
Бондаренко В.А., Николаев А.В., Шовгенов Д.А. Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях. Моделирование и анализ информационных систем. 2015;22(4):453-463. https://doi.org/10.18255/1818-1015-2015-4-453-463
For citation:
Bondarenko V.A., Nikolaev A.V., Shovgenov D.A. 1-Skeletons of the Spanning Tree Problems with Additional Constraints. Modeling and Analysis of Information Systems. 2015;22(4):453-463. (In Russ.) https://doi.org/10.18255/1818-1015-2015-4-453-463
Просмотров:
1129
Послать статью по эл. почте 