版权所有：内蒙古大学图书馆 技术提供：维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
为为班的统治集合问题的两分由小禁止的导致的 subgraphs 定义作者机构：Natl Res Univ Higher Sch Econ 25-12 Bolshaya Pecherskaya Ulitsa Nizhnii Novgorod 603155 Russia
出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)
年 卷 期：2016年第203卷
页 面：117-126页
核心收录：
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
基 金：Academic Fund Program at the National Research University Higher School of Economics (HSE) [15-01-0010] Government of the Russian Federation
主 题：Dominating set problem Hereditary class Computational complexity Polynomial-time algorithm
摘 要：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. (C) 2015 Elsevier B.V. All rights reserved.
