Open AccessAn Isomorphism Between Subexponential and Parameterized Complexity Theory
Author(s) -
Yijia Chen,
Martin Grohe
Publication year - 2007
Publication title -
siam journal on computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.533
H-Index - 122
eISSN - 1095-7111
pISSN - 0097-5397
DOI - 10.1137/070687153
Subject(s) - parameterized complexity , isomorphism (crystallography) , combinatorics , mathematics , computational complexity theory , complexity class , discrete mathematics , graph isomorphism , theoretical computer science , computer science , time complexity , algorithm , graph , chemistry , line graph , crystal structure , crystallography
We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom