咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Parameterized Problems Complet... 收藏
SSRN

Parameterized Problems Complete for Nondeterministic Fpt Time and Logarithmic Space

作     者:Bodlaender, Hans Leo Groenland, Carla Nederlof, Jesper Swennenhuis, Céline 

作者机构:Department of Information and Computing Sciences Utrecht University Netherlands Faculty of Electrical Engineering Mathematics and Computer Science Technical University Delft Netherlands Department of Mathematics and Computer Science Eindhoven University of Technology Eindhoven Netherlands 

出 版 物:《SSRN》 

年 卷 期:2023年

核心收录:

主  题:Bandwidth 

摘      要:Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time $f(k)n^{O(1)}$ and space $f(k)\log(n)$ (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloring andmPrecoloring Extension with pathwidth as parameter, Scheduling of Jobs with Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidth and variants of Weighted CNF-Satisfiability. In particular, this implies that all these problems are W[t]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem. © 2023, The Authors. All rights reserved.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分