A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

详细信息    查看全文

• 作者：D.S. Malyshev ^{dsmalyshev@rambler.ru" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Dominating set problem ; Hereditary class ; Computational complexity ; Polynomial-time algorithm
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 April 2016
• 年：2016
• 卷：203
• 期：Complete
• 页码：117-126
• 全文大小：691 K

文摘

We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.