On Problems as Hard as CNFSAT

In Journal of the ACM 9.1

“Dynamic programming treatment of the travelling salesman problem” · 1962

Earlier work this paper cites.

In Journal of the Society for Industrial and Applied Mathematics 10.1

“A dynamic programming approach to sequencing problems” · 1962

Earlier work this paper cites.

In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science, MFCS 1977 , 1977, pp. 162–176

“Graph-theoretic arguments in low-level complexity” · 1977

Earlier work this paper cites.

In Journal of Algorithms 7.3

“Algorithms for maximum independent sets” · 1986

Earlier work this paper cites.

In Journal of Computer and System Sciences 62.2

“On the complexity of k k -SAT” · 2000

Earlier work this paper cites.

In Journal of Computer and System Sciences 63.4

“Which problems have strongly exponential complexity?” · 2001

Earlier work this paper cites.

In Proceedings of the 18th Annual IEEE Conference on Computational Complexity, CCC 2003 , 2003, pp. 135

“The complexity of unique k k -SAT: An isolation lemma for k k -CNFs” · 2003

Earlier work this paper cites.

In Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 , 2004, pp. 245–256

“Exact (exponential) algorithms for the dominating set problem” · 2004

Earlier work this paper cites.

In Journal of Algorithms 54.1

“An algorithm for the satisfiability problem of formulas in conjunctive normal form” · 2004

Earlier work this paper cites.

In Information and Computing 201.2

“Tight lower bounds for certain parameterized NP-hard problems” · 2005

Earlier work this paper cites.

In Proceedings of the 21th Annual IEEE Conference on Computational Complexity, CCC 2006 , 2006, pp. 252–260

“A duality between clause width and clause density for SAT” · 2006

Cited alongside, same era.

In Proceedings of the 39th ACM Symposium on Theory of Computing, STOC 2007 , 2007, pp. 67–74

“Fourier meets Möbius: Fast subset convolution” · 2007

Cited alongside, same era.

In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 , 2007, pp. 338–348

“On the optimality of planar and geometric approximation schemes” · 2007

Cited alongside, same era.

URL: http://eccc.hpi-web.de/eccc-reports/2008/TR08-110/

“A lower bound on the size of series-parallel graphs dense in long paths”, 2008 · 2008

Cited alongside, same era.

In Proceedings of the 3rd International Workshop on Parameterized and Exact Computation, IWPEC 2008 , 2008, pp. 190–201

“The time complexity of constraint satisfaction” · 2008

Cited alongside, same era.

In Proceedings of the 36th Internationcal Colloquium on Automata, Languages and Programming, ICALP 2009 , 2009, pp. 713–725

“Fast polynomial-space algorithms using Möbius inversion: Improving on Steiner tree and related problems” · 2009

Later among the works it cites.

In Foundations and Trends in Theoretical Computer Science 5.1

“On the power of small-depth computation” · 2009

Later among the works it cites.

In Proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009 , 2009, pp. 554–565

“Inclusion/exclusion meets measure and conquer” · 2009

Later among the works it cites.

In Proceedings of the 5th International Symposium on Parameterized and Exact Computation, IPEC 2010 , 2010, pp. 204–215

“Inclusion/exclusion branching for partial dominating set and set splitting” · 2010

Later among the works it cites.

In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2011 , 2011, pp. 150–159

“Solving connectivity problems parameterized by treewidth in single exponential time” · 2011