Journal article

A Boundary Property for Upper Domination

  • AbouEisha, Hassan King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
  • Hussain, Shahid King Abdullah University of Science and Technology, Thuwal, Saudi Arabia
  • Lozin, Vadim Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK
  • Monnot, Jérôme CNRS, LAMSADE UMR 7243, University Paris-Dauphine, Paris, France
  • Ries, Bernard Université de Fribourg, Fribourg, Switzerland
  • Zamaraev, Viktor Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK
Show more…
    2016
Published in:
  • Lecture Notes in Computer Science. - 2016, vol. 9843, p. 229-240
English An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as P4-free graphs or 2K2-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating difficult instances of the problem from polynomially solvable ones consists of the so called boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/307831
Statistics

Document views: 5 File downloads:
  • ud-boundary_rero.pdf: 1