Yijia Chen, Martin Grohe,
"An Isomorphism between Subexponential and Parameterized Complexity Theory,"
Computational Complexity, Annual IEEE Conference on, pp. 314-330, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
BibTex
x
@article{
10.1109/CCC.2006.8, author = {Yijia Chen and Martin Grohe}, title = {An Isomorphism between Subexponential and Parameterized Complexity Theory}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2006}, issn = {1093-0159}, pages = {314-330}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.8}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }
RefWorks Procite/RefMan/Endnote
x
TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - An Isomorphism between Subexponential and Parameterized Complexity Theory SN - 1093-0159 SP314 EP330 A1 - Yijia Chen, A1 - Martin Grohe, PY - 2006 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -
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.
Citation:
Yijia Chen, Martin Grohe, "An Isomorphism between Subexponential and Parameterized Complexity Theory," ccc, pp.314-330, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb