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


Parameterized graph separation problems
Authors:  niel Marx
Affiliation:Department of Computer Science and Information Theory, Budapest University of Technology and Economics, H-1521 Budapest, Hungary
Abstract:We consider parameterized problems where some separation property has to be achieved by deleting as few vertices as possible. The following five problems are studied: delete k   vertices such that (a) each of the given ?? terminals is separated from the others, (b) each of the given ?? pairs of terminals is separated, (c) exactly ?? vertices are cut away from the graph, (d) exactly ?? connected vertices are cut away from the graph, (e) the graph is separated into at least ?? components. We show that if both k   and ?? are parameters, then (a), (b) and (d) are fixed-parameter tractable, while (c) and (e) are W[1]-hard.
Keywords:Parameterized complexity   Separator   Multicut   Multiway cut
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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