Width-Parametrized SAT: Time--Space Tradeoffs
by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang
Theory of Computing, Volume 10(12), pp. 297-339, 2014
Bibliography with links to cited articles
[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 NC1. 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]