{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T18:13:33Z","timestamp":1725732813608},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387081"},{"type":"electronic","value":"9783642387098"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44602-7_7","type":"book-chapter","created":{"date-parts":[[2014,8,23]],"date-time":"2014-08-23T01:18:40Z","timestamp":1408756720000},"page":"78-89","source":"Crossref","is-referenced-by-count":1,"title":["Treewidth Computation and Kernelization in the Parallel External Memory Model"],"prefix":"10.1007","author":[{"given":"Riko","family":"Jacob","sequence":"first","affiliation":[]},{"given":"Tobias","family":"Lieber","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"7_CR1","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms\u00a021(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"issue":"6","key":"7_CR2","doi-asserted-by":"publisher","first-page":"1725","DOI":"10.1137\/S0097539795289859","volume":"27","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., Hagerup, T.: Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput.\u00a027(6), 1725\u20131746 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"7_CR3","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s00453-007-9131-5","volume":"54","author":"A. Maheshwari","year":"2009","unstructured":"Maheshwari, A., Zeh, N.: I\/O-efficient algorithms for graphs and bounded treewidth. Algorithmica\u00a054(3), 413\u2013469 (2009)","journal-title":"Algorithmica"},{"key":"7_CR4","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer (2006)"},{"issue":"8","key":"7_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. System Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. System Sci."},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \n                    \n                      \n                    \n                    $\\mathcal{F}$\n                  -deletion: Approximation, kernelization and optimal FPT algorithms. In: Proc. FOCS 2012, pp. 470\u2013479 (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/978-3-642-39206-1_52","volume-title":"Automata, Languages, and Programming","author":"E.J. Kim","year":"2013","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 613\u2013624. Springer, Heidelberg (2013)"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. In: Proc. FOCS 2012, pp. 609\u2013618 (2012)","DOI":"10.1109\/FOCS.2012.71"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-3-642-28050-4_15","volume-title":"Parameterized and Exact Computation","author":"T. Hagerup","year":"2012","unstructured":"Hagerup, T.: Simpler linear-time kernelization for planar dominating set. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 181\u2013193. Springer, Heidelberg (2012)"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-28050-4_16","volume-title":"Parameterized and Exact Computation","author":"R. Bevern van","year":"2012","unstructured":"van Bevern, R., Hartung, S., Kammer, F., Niedermeier, R., Weller, M.: Linear-time computation of a linear problem kernel for dominating set on planar graphs. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 194\u2013206. Springer, Heidelberg (2012)"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Arge, L., Goodrich, M.T., Nelson, M., Sitchinava, N.: Fundamental parallel algorithms for private-cache chip multiprocessors. In: Proc. SPAA 2008, pp. 197\u2013206 (2008)","DOI":"10.1145\/1378533.1378573"},{"issue":"9","key":"7_CR12","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"issue":"6","key":"7_CR13","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proc. SODA 2010, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-32589-2_2","volume-title":"Mathematical Foundations of Computer Science 2012","author":"C. Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Niedermeier, R.: New races in parameterized algorithmics. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 19\u201330. Springer, Heidelberg (2012)"},{"key":"7_CR16","unstructured":"Greiner, G.: Sparse Matrix Computations and their I\/O Complexity. Dissertation, Technische Universit\u00e4t M\u00fcnchen (2012)"},{"key":"7_CR17","unstructured":"Chiang, Y.J., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proc. SODA, pp. 139\u2013149 (1995)"},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/3-540-36574-5_4","volume-title":"Algorithms for Memory Hierarchies","author":"I. Katriel","year":"2003","unstructured":"Katriel, I., Meyer, U.: Elementary graph algorithms in external memory. In: Meyer, U., Sanders, P., Sibeyn, J.F. (eds.) Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625, pp. 62\u201384. Springer, Heidelberg (2003)"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Arge, L., Goodrich, M.T., Sitchinava, N.: Parallel external memory graph algorithms. In: IPDPS, pp. 1\u201311 (2010)","DOI":"10.1109\/IPDPS.2010.5470440"},{"issue":"2","key":"7_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0022-0000(89)90042-1","volume":"39","author":"N. Dadoun","year":"1989","unstructured":"Dadoun, N., Kirkpatrick, D.G.: Parallel construction of subdivision hierarchies. J. Comput. Syst. Sci.\u00a039(2), 153\u2013165 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Vishkin, U.: Randomized speed-ups in parallel computation. In: Proc. STOC, pp. 230\u2013239 (1984)","DOI":"10.1145\/800057.808686"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M. (Meta) kernelization. In: Proc. FOCS, pp. 629\u2013638 (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. CoRR abs\/1207.0835 (2012)","DOI":"10.1007\/978-3-642-39206-1_52"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar \n                    \n                      \n                    \n                    $\\mathcal{F}$\n                  -deletion: Approximation and optimal FPT algorithms. CoRR abs\/1204.4230 (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"7_CR25","unstructured":"Jacob, R., Lieber, T., Sitchinava, N.: On the complexity of list ranking in the parallel external memory model. In: Proc. MFCS (to appear, 2014)"}],"container-title":["Lecture Notes in Computer Science","Advanced Information Systems Engineering"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44602-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T17:06:51Z","timestamp":1558976811000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44602-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642387081","9783642387098"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44602-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}