• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдена 21 публикация
Сортировка:
по названию
по году
Статья
Malyshev D. Discrete Applied Mathematics. 2016. Vol. 203. P. 117-126.
Добавлено: 9 октября 2015
Статья
Gurvich V., Boros E., Milanič M. et al. Discrete Applied Mathematics. 2018. Vol. 243. P. 21-38.
Добавлено: 10 октября 2018
Статья
Gurvich V., Vyalyi M. Discrete Applied Mathematics. 2012. Vol. 160. P. 1742-1756.
Добавлено: 18 октября 2014
Статья
Kuznetsov S., Babin M. A. Discrete Applied Mathematics. 2013. Vol. 161. No. 6. P. 742-749.

The problem of recognizing whether a subset of attributes is a premise of a minimal cover of functional dependencies of a relation is shown to be coNP-complete. The complexity of some related decision, enumerating, and sampling problems on functional dependencies, FCA implications, and closed sets of attributes is discussed.

Добавлено: 2 июня 2013
Статья
Alam M., Buzmakov A. V., Napoli A. Discrete Applied Mathematics. 2018. Vol. 249. P. 2-17.
Добавлено: 26 сентября 2017
Статья
Beaudou L., Foucaud F., Naserasr R. Discrete Applied Mathematics. 2019. Vol. 261. P. 40-51.
Добавлено: 8 июля 2019
Статья
Alekseev V. E., Mokeev D. B. Discrete Applied Mathematics. 2016. Vol. 204. P. 1-5.

Given a set X, a König graph G for X is a graph with the following property: for every induced subgraph H of G, the maximum number of vertex-disjoint induced subgraphs from X in H is equal to the minimum number of vertices whose deletion from H results in a graph containing no graph in X as an induced subgraph. The purpose of this paper is to characterize all König graphs for X, where X has only the 3-path or X consists of the 3-path and 3-cycle. We give also polynomial-time algorithms for the recognition of König graphs for the 3-path and for finding the corresponding packing and cover numbers in graphs of this type.

Добавлено: 12 ноября 2015
Статья
Gurvich V., Koshevoy G. Discrete Applied Mathematics. 2018. P. 1-15.
Добавлено: 10 октября 2018
Статья
Ignatov D. I. Discrete Applied Mathematics. 2018. Vol. 249. P. 74-84.
Добавлено: 15 декабря 2017
Статья
Gurvich V., Boros E., Milanic M. Discrete Applied Mathematics. 2015.
Добавлено: 11 марта 2017
Статья
Gurvich V., Oudalov V. Discrete Applied Mathematics. 2014. Vol. 167. P. 131-143.
Добавлено: 22 октября 2016
Статья
Gurvich V., Nhan Bao H. Discrete Applied Mathematics. 2018. Vol. 243. P. 54-72.
Добавлено: 7 февраля 2018
Статья
Cherkashin Danila, Kulikov A., Andrei Raigorodskii. Discrete Applied Mathematics. 2018. Vol. 243. P. 125-131.
Добавлено: 6 августа 2018
Статья
Gurvich V., Boros E., Kazuhisa M. et al. Discrete Applied Mathematics. 2018. Vol. 239. P. 1-14.
Добавлено: 26 октября 2017
Статья
Podolskii V. V., Hansen K. A., Ibsen-Jensen R. et al. Discrete Applied Mathematics. 2013. Vol. 161. No. 16-17. P. 2440-2459.
Добавлено: 18 декабря 2014
Статья
Vyalyi M., Tarasov S. Discrete Applied Mathematics. 2008. Vol. 156. P. 2070-2078.
Добавлено: 17 октября 2014
Статья
Kuznetsov S., Obiedkov S. Discrete Applied Mathematics. 2008. Vol. 156. No. 11. P. 1994-2003.
Добавлено: 6 марта 2009
Статья
Gribanov D., Malyshev D. Discrete Applied Mathematics. 2017. Vol. 227. P. 13-20.
Добавлено: 23 апреля 2017
Статья
Malyshev D. Discrete Applied Mathematics. 2018. Vol. 247. P. 423-432.
Добавлено: 23 апреля 2018
Статья
Malyshev D., Lobanova O. O. Discrete Applied Mathematics. 2017. Vol. 219. P. 158-166.
Добавлено: 21 ноября 2016
Статья
Lozin V. V., Malyshev D. Discrete Applied Mathematics. 2017. Vol. 216. P. 273-280.

We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm.

Добавлено: 3 марта 2015