ГРАНИЧНЫЕ КЛАССЫ ДЛЯ ЗАДАЧ НА ГРАФАХ |
| 6 | |
| 2008 |
| научная статья | 519.17 | ||
| 141-146 | вычислительная сложность, граничный класс. |
| Рассматривается понятие граничного класса, которое является полезным инструментом для анализа
вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся
задачи, для которых эти классы являются граничными. |
 |
| 1 . Алексеев В.Е., Малышев Д.С. Критерий граничности и его применения // Дискретный анализ и
исследование операций (принято к публикации). 2 . Alekseev V.E., Boliac R., Korobitsyn D.V., Lozin V.V. NP-hard graph problems and boundary classes of graphs // Theoretical Computer Science. 2007. V. 389. P. 219-236. 3 . Alekseev V.E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Applied Mathematics. 2004. V. 132. P. 17-26. 4 . Whitney H. Congruent graphs and the connectivity of graphs // Amer. J. Math. 1932. V. 54. P. 150-168. 5 . Харари Ф. Теория графов. М.: Мир, 1982. 6 . Lozin V.V., Rautenbach D. Оn the band-, tree- and clique-width of graphs with bounded vertex degree // SIAM J. Discrete Math. 2004. V. 18. P. 195-206. 7 . Chudnovsky M., Robertson N., Seymour P., Thomas R. The strong perfect graph theorem // Annal. of Math. 2006. V. 164. P. 51-229. 8 . Roussopoulos N. A max{m,n} algorithm for determining the graph H from its line graph G // Information Processing Letters. 1973. V. 2. ? 4. P. 108-112. 9 . Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 10 . Bodlaender H.L. Dynamic programming on graphs with bounded treewidth // LNCS. 1988. V. 317. P. 105-118. |