首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Boundary graph classes for some maximum induced subgraph problems
Authors:Dmitriy S Malyshev
Institution:1. National Research University Higher School of Economics, 25/12 Bolshaja Pecherskaja Ulitsa and 136 Rodionova Ulitsa, Nizhny Novgorod, 603155 and 603093, Russia
2. Department of Mathematical Logic and Higher Algebra, National Research University of Nizhny Novgorod, 23 Gagarina av., Nizhny Novgorod, 603950, Russia
Abstract:The notion of a boundary graph class was recently introduced for a classification of hereditary graph classes according to the complexity of a considered problem. Two concrete graph classes are known to be boundary for several graph problems. We formulate a criterion to determine whether these classes are boundary for a given graph problem or not. We also demonstrate that the classes are simultaneously boundary for some continuous set of graph problems and they are not simultaneously boundary for another set of the same cardinality. Both families of problems are constituted by variants of the maximum induced subgraph problem.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号