Pathwidth of cubic graphs and exact algorithms

Alber, 2002, Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33, 461, 10.1007/s00453-001-0116-5 Beigel, 1999, Finding maximum independent sets in sparse and general graphs, 856 Bezrukov, 2004, New spectral lower bounds on the bisection width of graphs, Theoret. Comput. Sci., 320, 155, 10.1016/j.tcs.2004.03.059 Bodlaender, 1998, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209, 1, 10.1016/S0304-3975(97)00228-4 Chen, 2003, Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems, vol. 2906, 148 Ellis, 1994, The vertex separation and search number of a graph, Inform. and Comput., 113, 50, 10.1006/inco.1994.1064 Fomin, 2005, Measure and conquer: Domination—a case study, vol. 3580, 191 Fomin, 2004, Exact (exponential) algorithms for the dominating set problem, vol. 3353, 245 Fomin, 2004, A simple and fast approach for solving problems on planar graphs, vol. 2996, 56 Gramm, 2003, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete Appl. Math., 130, 139, 10.1016/S0166-218X(02)00402-X F. Grandoni, Exact algorithms for hard graph problems, PhD thesis, Università di Roma “Tor Vergata”, Roma, Italy, March, 2004 F. Grandoni, A note on the complexity of minimum dominating set, J. Discrete Algorithms, in press Impagliazzo, 2001, Which problems have strongly exponential complexity, J. Comput. System Sci., 63, 512, 10.1006/jcss.2001.1774 Jansen, 2001, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs, vol. 2010, 365 Johnson, 1999, What are the least tractable instances of max independent set?, 927 J. Kneis, D. Mölle, S. Richter, P. Rossmanith, Algorithms based in treewidth of sparse graphs, in: Proc. 31st Internat. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), in: Lecture Notes in Comput. Sci., vol. 3787, Springer, Berlin, 2005, in press Kojevnikov, 2006, A new approach for proving upper bounds for MAX-2-SAT Kulikov, 2002, Solution of the maximum cut problem in time 2|E|/4, Zapiski Nauchnykh Seminarov (POMI), 293, 129 Monien, 2001, Upper bounds on the bisection width of 3- and 4-regular graphs, vol. 2136, 524 B. Randerath, I. Schiermeyer, Exact algorithms for MINIMUM DOMINATING SET, Technical Report zaik-469, Zentrum für Angewandte Informatik Köln, Germany, 2004 Reed, 1996, Paths, stars and the number three, Combin. Probab. Comput., 5, 277, 10.1017/S0963548300002042 Robertson, 1986, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309, 10.1016/0196-6774(86)90023-4 Robson Tarjan, 1977, Finding a maximum independent set, SIAM J. Comput., 6, 537, 10.1137/0206038 Williams, 2004, A new algorithm for optimal constraint satisfaction and its implications, vol. 3142, 1227