{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T04:08:31Z","timestamp":1769314111059,"version":"3.49.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,5,31]],"date-time":"2013-05-31T00:00:00Z","timestamp":1369958400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1007\/s00453-013-9796-x","type":"journal-article","created":{"date-parts":[[2013,5,30]],"date-time":"2013-05-30T17:36:24Z","timestamp":1369935384000},"page":"195-207","source":"Crossref","is-referenced-by-count":9,"title":["Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2 n"],"prefix":"10.1007","volume":"70","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,5,31]]},"reference":[{"key":"9796_CR1","first-page":"173","volume-title":"FOCS","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: FOCS, pp. 173\u2013182. IEEE Comput. Soc., Los Alamitos (2010)"},{"key":"9796_CR2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1250790.1250801","volume-title":"STOC","author":"A. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Johnson, D.S., Feige, U. (eds.) STOC, pp. 67\u201374. ACM, New York (2007)"},{"issue":"2","key":"9796_CR3","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"9796_CR4","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Analysis of data reduction: transformations give evidence for non-existence of polynomial kernels. Technical report UU-CS-2008-030, Institute of Information and Computing Sciences, Utrecht University, Netherlands (2008)"},{"key":"9796_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"IWPEC","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC. Lecture Notes in Computer Science, vol. 5917, pp. 75\u201385. Springer, Berlin (2009)"},{"issue":"40\u201342","key":"9796_CR6","doi-asserted-by":"crossref","first-page":"3701","DOI":"10.1016\/j.tcs.2010.06.018","volume":"411","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate bandwidth. Theor. Comput. Sci. 411(40\u201342), 3701\u20133713 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9796_CR7","first-page":"150","volume-title":"FOCS","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) FOCS, pp. 150\u2013159. IEEE Press, New York (2011)"},{"key":"9796_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/978-3-642-23719-5_26","volume-title":"ESA","author":"M. Cygan","year":"2011","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Scheduling partially ordered jobs faster than 2 n . In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA. Lecture Notes in Computer Science, vol.\u00a06942, pp. 299\u2013310. Springer, Berlin (2011)"},{"key":"9796_CR9","first-page":"74","volume-title":"IEEE Conference on Computational Complexity","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. In: IEEE Conference on Computational Complexity, pp. 74\u201384. IEEE Press, New York (2012)"},{"key":"9796_CR10","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":"ICALP (1)","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.) ICALP (1). Lecture Notes in Computer Science, vol. 5555, pp. 378\u2013389. Springer, Berlin (2009)"},{"key":"9796_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F. Fomin","year":"2010","unstructured":"Fomin, F., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"issue":"5","key":"9796_CR12","first-page":"1","volume":"56","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J.\u00a0ACM 56(5), 1\u201332 (2009)","journal-title":"J.\u00a0ACM"},{"key":"9796_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-23719-5_25","volume-title":"ESA","author":"F.V. Fomin","year":"2011","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Exact algorithm for the maximum induced planar subgraph problem. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA. Lecture Notes in Computer Science, vol. 6942, pp. 287\u2013298. Springer, Berlin (2011)"},{"issue":"7","key":"9796_CR14","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1016\/j.comgeo.2012.02.002","volume":"45","author":"C. Gray","year":"2012","unstructured":"Gray, C., Kammer, F., L\u00f6ffler, M., Silveira, R.I.: Removing local extrema from imprecise terrains. Comput. Geom. 45(7), 334\u2013349 (2012)","journal-title":"Comput. Geom."},{"issue":"2","key":"9796_CR15","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9796_CR16","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/1.9781611973082.61","volume-title":"Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Known algorithms on graphs of bounded treewidth are probably optimal. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 777\u2013789 (2011)"},{"key":"9796_CR17","first-page":"1065","volume-title":"SODA","author":"M. P\u0103tra\u015fcu","year":"2010","unstructured":"P\u0103tra\u015fcu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Charikar, M. (ed.) SODA, pp. 1065\u20131075. SIAM, Philadelphia (2010)"},{"issue":"48","key":"9796_CR18","doi-asserted-by":"crossref","first-page":"6761","DOI":"10.1016\/j.tcs.2011.09.001","volume":"412","author":"D. Paulusma","year":"2011","unstructured":"Paulusma, D., van Rooij, J.M.M.: On partitioning a graph into two connected subgraphs. Theor. Comput. Sci. 412(48), 6761\u20136769 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9796_CR19","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XIII. The disjoint paths problem. J. Comb. Theory, Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9796_CR20","doi-asserted-by":"crossref","unstructured":"Telle, J.A., Villanger, Y.: Connecting terminals and 2-disjoint connected subgraphs. (2013). arXiv:1301.2506v1","DOI":"10.1007\/978-3-642-45043-3_36"},{"key":"9796_CR21","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":"ESA","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.) ESA. Lecture Notes in Computer Science, vol. 5757, pp. 554\u2013565. Springer, Berlin (2009)"},{"issue":"47\u201349","key":"9796_CR22","doi-asserted-by":"crossref","first-page":"4834","DOI":"10.1016\/j.tcs.2009.06.028","volume":"410","author":"P. \u2019t\u00a0Hof van","year":"2009","unstructured":"van\u00a0\u2019t\u00a0Hof, P., Paulusma, D., Woeginger, G.J.: Partitioning graphs into connected parts. Theor. Comput. Sci. 410(47\u201349), 4834\u20134843 (2009)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9796-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9796-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9796-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,2]],"date-time":"2023-07-02T01:13:41Z","timestamp":1688260421000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9796-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,31]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["9796"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9796-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,31]]}}}