Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen

被引：0

作者：

Fellows, Michael Ralph ^{[1
]}

机构：

[1] Charles Darwin Univ, Engn & IT, Darwin, NT 0909, Australia

来源：

TSINGHUA SCIENCE AND TECHNOLOGY | 2014年 / 19卷 / 04期

基金：

澳大利亚研究理事会;

关键词：

parameterized complexity; multivariate algorithmics; open problems; LOWER BOUNDS; NONDETERMINISM;

D O I：

10.1109/TST.2014.6867514

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This short paper highlights some open problems related to the work of Jianer Chen in the area of parameterized/multivariate algorithmics.

引用

页码：325 / 328

页数：4

共 27 条

[1]

[Anonymous], 2013, TEXTS COMPUTER SCI, DOI DOI 10.1007/978-1-4471-5559-1

[2]

Bazgan C., 1995, THESIS

[3]

Bodlaender H. L., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P449, DOI 10.1145/195058.195229

[4] On problems without polynomial kernels [J].

Bodlaender, Hans L. ;

Downey, Rodney G. ;

Fellows, Michael R. ;

Hermelin, Danny .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2009, 75 (08) :423-434

[5]

BODLAENDER HL, 1992, LECT NOTES COMPUT SC, V570, P230

[6] NP-Hard sets are exponentially dense unless coNP ⊆ NP/poly [J].

Buhrman, Harry ;

Hitchcock, John M. .

TWENTY-THIRD ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2008, :1-+

[7] NONDETERMINISM WITHIN P [J].

BUSS, JF ;

GOLDSMITH, J .

SIAM JOURNAL ON COMPUTING, 1993, 22 (03) :560-572

[8]

Cai L., 1993, Proceedings of the 2nd Israel Symposium on Theory and Computing Systems (Cat. No.93TH0520-7), P118, DOI 10.1109/ISTCS.1993.253478

[9]

Cai L., 1992, PROJECT REPORT

[10] On the parameterized complexity of short computation and factorization [J].

Cai, LM ;

Chen, JN ;

Downey, RG ;

Fellows, MR .

ARCHIVE FOR MATHEMATICAL LOGIC, 1997, 36 (4-5) :321-337

← 1 2 3 →