{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:20:21Z","timestamp":1759335621164},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,9,14]],"date-time":"2011-09-14T00:00:00Z","timestamp":1315958400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00453-011-9566-6","type":"journal-article","created":{"date-parts":[[2011,9,13]],"date-time":"2011-09-13T17:48:57Z","timestamp":1315936137000},"page":"189-212","source":"Crossref","is-referenced-by-count":5,"title":["Parameterized Measure & Conquer for Problems with No Small Kernels"],"prefix":"10.1007","volume":"64","author":[{"given":"Daniel","family":"Binkele-Raible","sequence":"first","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,14]]},"reference":[{"key":"9566_CR1","first-page":"62","volume-title":"Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics","author":"F.N. Abu-Khzam","year":"2004","unstructured":"Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Sutters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: theory and experiments. In: Arge, L., Italiano, G.F., Sedgewick, R. (eds.) Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics pp. 62\u201369. SIAM, Philadelphia (2004)"},{"key":"9566_CR2","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1016\/j.jda.2010.06.001","volume":"8","author":"D. Binkele-Raible","year":"2010","unstructured":"Binkele-Raible, D., Fernau, H.: A new upper bound for Max-2-SAT: a graph-theoretic approach. J.\u00a0Discrete Algorithms 8, 388\u2013401 (2010)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9566_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/978-3-642-17493-3_6","volume-title":"Parameterized and Exact Computation (IPEC 2010)","author":"D. Binkele-Raible","year":"2010","unstructured":"Binkele-Raible, D., Fernau, H.: Enumerate and measure, improving parameter budget management. In: Raman, V., Saurabh, S. (eds.) Parameterized and Exact Computation (IPEC 2010). Lecture Notes in Computer Science, vol. 6478, pp. 38\u201349. Springer, Berlin (2010)"},{"key":"9566_CR4","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00453-004-1145-7","volume":"43","author":"J. Chen","year":"2005","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Labeled search trees and amortized analysis: improved upper bounds for NP-hard problems. Algorithmica 43, 245\u2013273 (2005)","journal-title":"Algorithmica"},{"key":"9566_CR5","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/j.jcss.2009.06.005","volume":"76","author":"J. Daligault","year":"2010","unstructured":"Daligault, J., Gutin, G., Kim, E.J., Yeo, A.: FPT algorithms and kernels for the directed k-leaf problem. J. Comput. Syst. Sci. 76, 144\u2013152 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9566_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I. Lecture Notes in Computer Science, vol. 5555, pp. 378\u2013389. Springer, Berlin (2009)"},{"key":"9566_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"9566_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/11847250_13","volume-title":"International Workshop on Parameterized and Exact Computation (IWPEC 2006)","author":"H. Fernau","year":"2006","unstructured":"Fernau, H.: Edge dominating set: efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M. (eds.) International Workshop on Parameterized and Exact Computation (IWPEC 2006). Lecture Notes in Computer Science, vol. 4169, pp. 142\u2013153. Springer, Berlin (2006)"},{"key":"9566_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/978-3-642-14031-0_6","volume-title":"International Computing and Combinatorics Conference (COCOON 2010)","author":"H. Fernau","year":"2010","unstructured":"Fernau, H., Fomin, F.V., Philip, G., Saurabh, S.: The curse of connectivity: t-total vertex (edge) cover. In: Thai, M.T., Sahni, S. (eds.) International Computing and Combinatorics Conference (COCOON 2010). Lecture Notes in Computer Science, vol. 6196, pp. 34\u201343. Springer, Berlin (2010)"},{"key":"9566_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/978-3-642-11409-0_9","volume-title":"Graph-Theoretic Concepts in Computer Science (WG 2009)","author":"H. Fernau","year":"2010","unstructured":"Fernau, H., Gaspers, S., Raible, D.: Exact and parameterized algorithms for Max Internal Spanning Tree. In: Paul, C., Habib, M. (eds.) Graph-Theoretic Concepts in Computer Science (WG 2009). Lecture Notes in Computer Science, vol. 5911, pp. 100\u2013111. Springer, Berlin (2010). Long version accepted for publication with Algorithmica"},{"key":"9566_CR11","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.jda.2008.09.007","volume":"7","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Manlove, D.F.: Vertex and edge covers with clustering properties: Complexity and algorithms. J. Discrete Algorithms 7, 149\u2013167 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"9566_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1007\/978-3-540-77891-2_14","volume-title":"Workshop on Algorithms and Computation (WALCOM 2008)","author":"H. Fernau","year":"2008","unstructured":"Fernau, H., Raible, D.: Exact algorithms for maximum acyclic subgraph on a superclass of cubic graphs. In: Nakano, S.-I., Rahman, Md.S. (eds.) Workshop on Algorithms and Computation (WALCOM 2008). Lecture Notes in Computer Science, vol. 4921, pp. 144\u2013156. Springer, Berlin (2008)"},{"key":"9566_CR13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54, 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"9566_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A Measure & Conquer approach for the analysis of exact algorithms. J. ACM 56(5) (2009)","DOI":"10.1145\/1552285.1552286"},{"key":"9566_CR15","series-title":"Texts in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, Berlin (2010)"},{"key":"9566_CR16","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0020-0190(01)00138-7","volume":"79","author":"T. Fujito","year":"2001","unstructured":"Fujito, T.: On approximability of the independent\/connected edge dominating set problems. Inf. Process. Lett. 79, 261\u2013266 (2001)","journal-title":"Inf. Process. Lett."},{"key":"9566_CR17","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/j.ipl.2004.01.011","volume":"90","author":"T. Fujito","year":"2004","unstructured":"Fujito, T., Doi, T.: A 2-approximation NC algorithm for connected vertex cover and tree cover. Inf. Process. Lett. 90, 59\u201363 (2004)","journal-title":"Inf. Process. Lett."},{"key":"9566_CR18","unstructured":"Gaspers, S.: Measure & Conquer for parameterized branching algorithms. Parameterized Complexity News from September 2009 (pp. 5\u20136)"},{"key":"9566_CR19","first-page":"606","volume-title":"Symposium on Discrete Algorithms (SODA 2009)","author":"S. Gaspers","year":"2009","unstructured":"Gaspers, S., Sorkin, G.B.: A universally fastest algorithms for Max 2-Sat, Max 2-CSP, and everything in between. In: Symposium on Discrete Algorithms (SODA 2009), pp. 606\u2013615. ACM Press, New York (2009)"},{"key":"9566_CR20","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput. Syst. 41, 501\u2013520 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9566_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/978-3-540-92182-0_26","volume-title":"International Symposium on Algorithms and Computation (ISAAC 2008)","author":"J. Kneis","year":"2008","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A new algorithm for finding trees with many leaves. In: International Symposium on Algorithms and Computation (ISAAC 2008). Lecture Notes in Computer Science, vol. 5369, pp. 270\u2013281. Springer, Berlin (2008)"},{"key":"9566_CR22","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/s00224-007-9089-3","volume":"43","author":"D. M\u00f6lle","year":"2008","unstructured":"M\u00f6lle, D., Richter, S., Rossmanith, P.: Enumerate and expand: improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst. 43, 234\u2013253 (2008)","journal-title":"Theory Comput. Syst."},{"key":"9566_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/978-3-642-02927-1_59","volume-title":"International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I","author":"J. Nederlof","year":"2009","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using M\u00f6bius inversion: improving on Steiner tree and related problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) International Colloquium on Automata, Languages and Programming (ICALP 2009), Part I. Lecture Notes in Computer Science, vol. 5555, pp. 713\u2013725. Springer, Berlin (2009)"},{"key":"9566_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, London (2006)"},{"key":"9566_CR25","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0012-365X(84)90170-5","volume":"49","author":"J. Plesn\u00edk","year":"1984","unstructured":"Plesn\u00edk, J.: Equivalence between the minimum covering problem and the maximum matching problem. Discrete Math. 49, 315\u2013317 (1984)","journal-title":"Discrete Math."},{"key":"9566_CR26","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0166-218X(99)00052-9","volume":"92","author":"J. Plesn\u00edk","year":"1999","unstructured":"Plesn\u00edk, J.: Constrained weighted matchings and edge coverings in graphs. Discrete Appl. Math. 92, 229\u2013241 (1999)","journal-title":"Discrete Appl. Math."},{"key":"9566_CR27","unstructured":"Prieto, E.: Systematic kernelization in FPT algorithm design. PhD thesis, The University of Newcastle, Australia (2005)"},{"key":"9566_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1007\/978-3-642-11266-9_56","volume-title":"Theory and Practice of Computer Science, Software Seminar (SOFSEM 2010)","author":"D. Raible","year":"2010","unstructured":"Raible, D., Fernau, H.: An amortized search tree analysis for k-Leaf Spanning Tree. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorn\u00fd, J., Rumpe, B. (eds.) Theory and Practice of Computer Science, Software Seminar (SOFSEM 2010). Lecture Notes in Computer Science, vol. 5901, pp. 672\u2013684. Springer, Berlin (2010)"},{"key":"9566_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/11560586_30","volume-title":"Italian Conference on Theoretical Computer Science (ICTCS 2005)","author":"V. Raman","year":"2005","unstructured":"Raman, V., Saurabh, S., Sikdar, S.: Improved exact exponential algorithms for vertex bipartization and other problems. In: Coppo, M., Lodi, E., Pinna, G.M. (eds.) Italian Conference on Theoretical Computer Science (ICTCS 2005). Lecture Notes in Computer Science, vol. 3701, pp. 375\u2013389. Springer, Berlin (2005)"},{"issue":"2","key":"9566_CR30","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.jda.2008.09.004","volume":"7","author":"I. Razgon","year":"2009","unstructured":"Razgon, I.: Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3. J. Discrete Algorithms 7(2), 191\u2013212 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"9566_CR31","series-title":"LIPIcs","first-page":"657","volume-title":"International Symposium on Theoretical Aspects of Computer Science (STACS 2008)","author":"J.M.M. Rooij van","year":"2008","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Design by Measure and Conquer, a faster exact algorithm for dominating set. In: Albers, S., Weil, P. (eds.) International Symposium on Theoretical Aspects of Computer Science (STACS 2008). LIPIcs, vol. 1, pp. 657\u2013668. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Hamburg (2008)"},{"key":"9566_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/978-3-540-79723-4_20","volume-title":"Parameterized and Exact Computation (IWPEC 2008)","author":"J.M.M. Rooij van","year":"2008","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for edge domination. In: Grohe, M., Niedermeier, R. (eds.) Parameterized and Exact Computation (IWPEC 2008). Lecture Notes in Computer Science, vol. 5018, pp. 214\u2013225. Springer, Berlin (2008). Details on the parameterized algorithm can be found in the TR version. The long version was accepted for publication with Algorithmica"},{"key":"9566_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1007\/978-3-642-04128-0_50","volume-title":"Algorithms\u2014ESA 2009, 17th Annual European Symposium","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/exclusion meets Measure and Conquer. In: Fiat, A., Sanders, P. (eds.) Algorithms\u2014ESA 2009, 17th Annual European Symposium. Lecture Notes in Computer Science, vol. 5757, pp. 554\u2013565. Springer, Berlin (2009)"},{"key":"9566_CR34","unstructured":"Truss, A., Weller, M.: Lessons in magic: AGAPE Spring School (May 24\u201329, Corsica). Parameterized Complexity News from September 2009 (pp. 2\u20133; supplemented by Fig. 1 on p.\u00a01)"},{"key":"9566_CR35","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38, 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9566-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9566-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9566-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:08Z","timestamp":1559137508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9566-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,14]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["9566"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9566-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,14]]}}}