Исследована алгоритмическая сложность задачи о поиске семейства простых циклов, обходящих каждую вершину орграфа с полустепенями вершин, не превосходящими k, при наличии дополнительных ограничений на вид списка смежности. Рассмотрены поисковый и оптимизационный её варианты. Показана параметрически полиномиальная разрешимость задачи в обоих вариантах, предложены алгоритмы со временем работы O(nk2 + n log2 n), O(n(k2 + k) + n log2 n) и O(n) для различных типов ограничений; n - количество вершин орграфа.
Скачать электронную версию публикации
Загружен, раз: 6
- Title Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k
- Headline Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 60
- Date:
- DOI 10.17223/20710410/60/7
Ключевые слова
ориентированные графы, простые циклы, задачи поиска, оптимизация, класс P, параметрическая сложность, полиномиальная разрешимостьАвторы
Ссылки
Karp R.M. Reducibility among combinatorial problems // R.E. Miller, J. W. Thatcher, J.D. Bohlinger (eds).Complexity of Computer Computations. The IBM Research Symposia Series. Boston: Springer, 1972. P. 85-103.
Akiyama T., Nisizeki T., and Saito N. NP-completeness of the Hamiltonian cycle problem for bipartite graphs //j. Inform. Processing. 1981. V. 3. No. 2. P.73-76.
Itai A., Papadimitiou Ch., and Szwarcfiter J. Hamiltonian paths in grid graphs // SIAM J.Computing. 1982. V. 4. No. 11. P.676-686.
Buro M. Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs // LNCS. 2000. V. 2063. P.250-261.
Plesnik J. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two // Inform. Process. Lett. 1979. V. 8. No. 4. P. 199-201.
Chiba N. and Nishizeki T. The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs //j. Algorithms. 1989. V. 10. No. 2. P. 187-211.
Dirac G. A. Some theorems on abstract graphs // Proc. London Math. Soc. 1952. V. 2. No. 3. P. 69-81.
Ore O. Note on Hamiltonian circuits // American Math. Monthly. 1960. V. 67. P.55.
Ghouila-Houri A. Une condition suffisante d'existence d'un circuit Hamiltonien // Comptes Rendus de l'Academie des Science Paris. 1960. V.251. P.495-497.
Woodall D. Sufficient conditions for cycles in digraphs // Proc. London Math. Soc. 1972. V. 24. P. 739-755.
Christofides D., Keevash P., Kiihn D., and Osthus D. A semi-exact degree condition for Hamiltonian cycles in digraphs // SIAM J. Discrete Math. 2010. V.24. No.3. P.709-756.
Keevash P., Kiihn D., and Osthus D. An exact minimum degree condition for Hamiltonian cycles in oriented graphs //j. London Math. Soc. 2009. V. 79. No. 1. P. 144-166.
Kelly L., Kuhn D., and Osthus D. A Dirac-type result on Hamiltonian cycles in oriented graphs // Combinatorics, Probability and Computing. 2008. V. 17. No. 5. P.689-709.
Bjorklund A., Husfeldt T., and Khanna S. Approximating longest directed paths and cycles // Automata, Languages and Programming. 2004. V. 3142. P.222-233.
Gabow H. N. and Nie S. Finding long paths, cycles and circuits // LNCS. 2008. V. 5369. P. 752-763.
Zamfirescu T. On longest paths and circuits in graphs // Mathematica Scandinavica. 1976. V. 38. P.211-239.
Харари Ф. Теория графов. М.: Едиториал УРСС, 2003. 296 с.
Медведев А. А. Поиск семейства простых циклов в орграфе с полустепенями вершин, не превосходящими 2 // Интеллектуальные системы. Теория и приложения. 2022. Т. 26. №3. С. 150-164.
Kuhn H. W. Variants of the Hungarian method for assignment problems // Naval Research Logistics Quarterly. 1956. V. 3. P. 253-258.
Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/7
Скачать полнотекстовую версию
Загружен, раз: 125