[1]   Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, and Klaus W. Wagner: Characterizing small depth and small space classes by operators of higher type. Chicago J. Theor. Comput. Sci, 2000(2), 2000. CJTCS.

[2]   Michael Alekhnovich and Alexander A. Razborov: Satisfiability, branch-width and Tseitin tautologies. In Proc. 43rd FOCS, pp. 593–603. IEEE Comp. Soc. Press, 2002. See also journal version in Comput. Complexity 20(4), 2011, 649-678. [doi:10.1109/SFCS.2002.1181983]

[3]   Sanjeev Arora and Boaz Barak: Computational complexity: a modern approach. Volume 1. Cambridge Univ. Press, 2009. [doi:10.1017/CBO9780511804090]

[4]   Fahiem Bacchus, Shannon Dalmao, and Toniann Pitassi: Solving #SAT and Bayesian inference with backtracking search. J. Artif. Intell. Res. (JAIR), 34:391–442, 2009. Preliminary version in FOCS’03. [doi:10.1613/jair.2648]

[5]   David A. Mix Barrington, Neil Immerman, and Howard Straubing: On uniformity within NC¹. J. Comput. System Sci., 41(3):274–306, 1990. [doi:10.1016/0022-0000(90)90022-D]

[6]   Paul Beame, Christopher Beck, and Russell Impagliazzo: Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space. In Proc. 44th STOC, pp. 213–232. ACM Press, 2012. See also at ECCC. [doi:10.1145/2213977.2213999]

[7]   Hans L. Bodlaender: A tourist guide through treewidth. Acta Cybern., 11(1-2):1–22, 1993. See at Act Cybernetica. [http:citeseerx.ist.psu.eduviewdocsummary?doi=10.1.1.18.8755]

[8]   Hans L. Bodlaender: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1-2):1–45, 1998. [doi:10.1016/S0304-3975(97)00228-4]

[9]   Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos: A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems, 50(3):420–432, 2012. [doi:10.1007/s00224-011-9312-0]

[10]   Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, and Ton Kloks: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms, 18(2):238–255, 1995. [doi:10.1006/jagm.1995.1009]

[11]   Ronald V. Book, Christopher B. Wilson, and Xu Mei-Rui: Relativizing time, space, and time-space. SIAM J. Comput., 11(3):571–581, 1982. [doi:10.1137/0211048]

[12]   Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompa: Two applications of inductive counting for complementation problems. SIAM J. Comput., 18(3):559–578, 1989. Preliminary version in SCTC’88 Erratum in SICOMP. [doi:10.1137/0218038]

[13]   Stephen A. Cook: Characterizations of pushdown machines in terms of time-bounded computers. J. ACM, 18(1):4–18, 1971. Preliminary version in STOC’69. [doi:10.1145/321623.321625]

[14]   Stephen A. Cook: A taxonomy of problems with fast parallel algorithms. Inf. Control, 64(1-3):2–22, 1985. Preliminary version in FCT’83. [doi:10.1016/S0019-9958(85)80041-3]

[15]   Stephen A. Cook and Robert A. Reckhow: The relative efficiency of propositional proof systems. J. Symbolic Logic, 44(1):36–50, 1979. Preliminary version in STOC’74. [doi:10.2307/2273702]

[16]   Eldar Fischer, Johann A. Makowsky, and Elena V. Ravve: Counting truth assignments of formulas of bounded tree-width or clique-width. Discr. Appl. Math., 156(4):511–529, 2008. [doi:10.1016/j.dam.2006.06.020]

[17]   Fedor V. Fomin, Fabrizio Grandoni, Daniel Lokshtanov, and Saket Saurabh: Sharp separation and applications to exact and parameterized algorithms. Algorithmica, 63(3):692–706, 2012. Preliminary version in LATIN’10. [doi:10.1007/s00453-011-9555-9]

[18]   Fedor V. Fomin and Dieter Kratsch: Exact Exponential Algorithms. Springer, 2010. [doi:10.1007/978-3-642-16533-7]

[19]   Konstantinos Georgiou and Periklis A. Papakonstantinou: Complexity and algorithms for well-structured k-SAT instances. In Theory and Applications of Satisfiability Testing - SAT 2008, volume 4996 of LNCS, pp. 105–118. Springer, 2008. [doi:10.1007/978-3-540-79719-7_10]

[20]   Georg Gottlob, Nicola Leone, and Francesco Scarcello: The complexity of acyclic conjunctive queries. J. ACM, 48(3):431–498, 2001. Preliminary version in FOCS’98. [doi:10.1145/382780.382783]

[21]   Martin Grohe: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1–24, 2007. Preliminary version in FOCS’03. [doi:10.1145/1206035.1206036]

[22]   Russell Impagliazzo, Ramamohan Paturi, and Francis Zane: Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001. Preliminary version in FOCS’98. [doi:10.1006/jcss.2001.1774]

[23]   Ton Kloks: Treewidth, Computations and Approximations. Volume 842 of Lecture Notes in Computer Science. Springer, 1994. [doi:10.1007/BFb0045375]

[24]   Mikko Koivisto and Pekka Parviainen: A space-time tradeoff for permutation problems. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 484–492. ACM Press, 2010. [doi:10.1137/1.9781611973075.41]

[25]   Daniel Lokshtanov, Dániel Marx, and Saket Saurabh: Known algorithms on graphs on bounded treewidth are probably optimal. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 777–789, 2011. [doi:10.1137/1.9781611973082.61, arXiv:1007.5450]

[26]   Daniel Lokshtanov, Matthias Mnich, and Saket Saurabh: Planar k-path in subexponential time and polynomial space. In Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, pp. 262–270, 2011. [doi:10.1007/978-3-642-25870-1_24]

[27]   Dániel Marx: Can you beat treewidth? Theory of Computing, 6(5):85–112, 2010. Preliminary version in FOCS’07. [doi:10.4086/toc.2010.v006a005]

[28]   Robin A. Moser and Dominik Scheder: A full derandomization of Schöning’s k-SAT algorithm. In Proc. 43rd STOC, pp. 245–252. ACM Press, 2011. [doi:10.1145/1993636.1993670, arXiv:1008.4067]

[29]   Rolf Niedermeier and Peter Rossmanith: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits. Inform. and Comput., 118(2):227–245, 1995. Preliminary version in LATIN’92. [doi:10.1006/inco.1995.1064]

[30]   Periklis A. Papakonstantinou: A note on width-parameterized SAT: An exact machine-model characterization. Inform. Process. Lett., 110(1):8–12, 2009. [doi:10.1016/j.ipl.2009.09.012]

[31]    Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane: An improved exponential-time algorithm for k-SAT. J. ACM, 52(3):337–364, 1998. Preliminary version in FOCS’98. [doi:10.1145/1066100.1066101]

[32]   Neil Robertson and Paul D. Seymour: Graph minors. I. excluding a forest. J. Comb. Theory, Ser. B, 35(1):39–61, 1983. [doi:10.1016/0095-8956(83)90079-5]

[33]   Neil Robertson and Paul D. Seymour: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986. [doi:10.1016/0196-6774(86)90023-4]

[34]   Walter L. Ruzzo: Tree-size bounded alternation. J. Comput. System Sci., 21(2):218–235, 1980. Preliminary version in STOC’79. [doi:10.1016/0022-0000(80)90036-7]

[35]   Marko Samer and Stefan Szeider: Algorithms for propositional model counting. J. Discrete Algorithms, 8(1):50–64, 2010. Preliminary version in LPAR’07. [doi:10.1016/j.jda.2009.06.002]

[36]   Uwe Schöning: A probabilistic algorithm for k-SAT based on limited local search and restart. Algorithmica, 32(4):615–623, 2002. Preliminary version in FOCS’99. [doi:10.1007/s00453-001-0094-7]

[37]   Stefan Szeider: On fixed-parameter tractable parameterizations of SAT. In Theory and Applications of Satisfiability Testing - SAT 2003, volume 2919 of LNCS, pp. 188–202, 2003. [doi:10.1007/978-3-540-24605-3_15]

[38]   H. Venkateswaran: Properties that characterize LOGCFL. J. Comput. Syst. Sci., 43(2):380–404, 1991. Conference version in STOC’87. [doi:10.1016/0022-0000(91)90020-6]

[39]   Heribert Vollmer: Introduction to Circuit Complexity. Springer, 1999. [doi:10.1007/978-3-662-03927-4]

[40]   Gerhard J. Woeginger: Exact algorithms for NP-hard problems: A survey. Combinatorial Optimization—Eureka, You Shrink!, 2570:185–207, 2003. [doi:10.1007/3-540-36478-1_17]