• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 28
Sort:
by name
by year
Article
Borchmann D., Hanika T., Obiedkov S. Discrete Applied Mathematics. 2020. Vol. 273. P. 30-42.

We propose an algorithm for learning the Horn envelope of an arbitrary domain using an expert, or an oracle, capable of answering certain types of queries about this domain. Attribute exploration from formal concept analysis is a procedure that solves this problem, but the number of queries it may ask is exponential in the size of the resulting Horn formula in the worst case. We recall a well-known polynomial-time algorithm for learning Horn formulas with membership and equivalence queries and modify it to obtain a polynomial-time probably approximately correct algorithm for learning the Horn envelope of an arbitrary domain.

Added: Oct 29, 2019
Article
Vyalyi M., Tarasov S. Discrete Applied Mathematics. 2008. Vol. 156. P. 2070-2078.
Added: Oct 17, 2014
Article
Kuznetsov S., Obiedkov S. Discrete Applied Mathematics. 2008. Vol. 156. No. 11. P. 1994-2003.
Added: Mar 6, 2009
Article
Gribanov D., Malyshev D. Discrete Applied Mathematics. 2017. Vol. 227. P. 13-20.

We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value

Added: Apr 23, 2017
Article
Malyshev D. Discrete Applied Mathematics. 2018. Vol. 247. P. 423-432.

We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights.

Added: Apr 23, 2018
Article
Malyshev D., Lobanova O. O. Discrete Applied Mathematics. 2017. Vol. 219. P. 158-166.

We show that the chromatic number of {P_5,K_p-e}-free graphs can be computed in polynomial time for each fixed p.

Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P_5,co(P_3+P_2)}-free graphs.

Added: Nov 21, 2016
Article
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.

Added: Mar 3, 2015
1 2