{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:30:11Z","timestamp":1725456611873},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_33","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T04:42:25Z","timestamp":1350880945000},"page":"332-343","source":"Crossref","is-referenced-by-count":0,"title":["On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[]},{"given":"Pim","family":"van\u2019t Hof","sequence":"additional","affiliation":[]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042, 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"33_CR2","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. Syst. Sci.\u00a075, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization. In: FOCS 2009, pp. 629\u2013638. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.46"},{"issue":"35","key":"33_CR4","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci.\u00a0412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: Fortnow, L., Vadhan, S.P. (eds.) STOC 2011, pp. 459\u2013468. ACM (2011)","DOI":"10.1145\/1993636.1993698"},{"key":"33_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/978-3-540-73951-7_43","volume-title":"Algorithms and Data Structures","author":"J. Chen","year":"2007","unstructured":"Chen, J., Liu, Y., Lu, S.: An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 495\u2013506. Springer, Heidelberg (2007)"},{"key":"33_CR7","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics","author":"B. Courcelle","year":"1990","unstructured":"Courcelle, B.: Graph rewriting: an algebraic and logic approach. In: Van Leeuwen (ed.) Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pp. 193\u2013242. Elsevier and MIT Press, Amsterdam (1990)"},{"key":"33_CR8","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory. Electronic Edition (2005)","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"33_CR9","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"33_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S. Dreyfus","year":"1971","unstructured":"Dreyfus, S., Wagner, R.: The Steiner problem in graphs. Networks\u00a01, 195\u2013207 (1971)","journal-title":"Networks"},{"key":"33_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U., Mahdian, M.: Finding small balanced separators. In: Kleinberg, J.M. (ed.) STOC 2006, pp. 375\u2013384. ACM (2006)","DOI":"10.1145\/1132516.1132573"},{"key":"33_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Charikar, M. (ed.) SODA 2010, pp. 503\u2013510. SIAM (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"33_CR13","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L. Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci.\u00a077, 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"33_CR14","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.ipl.2007.03.005","volume":"103","author":"G. Gottlob","year":"2007","unstructured":"Gottlob, G., Lee, S.T.: A logical approach to multicut problems. Inform. Process. Lett.\u00a0103(4), 136\u2013141 (2007)","journal-title":"Inform. Process. Lett."},{"key":"33_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-540-79723-4_13","volume-title":"Parameterized and Exact Computation","author":"S. Guillemot","year":"2008","unstructured":"Guillemot, S.: FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 129\u2013140. Springer, Heidelberg (2008)"},{"issue":"2","key":"33_CR16","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.ejor.2007.02.014","volume":"186","author":"J. Guo","year":"2008","unstructured":"Guo, J., H\u00fcffner, F., Kenar, E., Niedermeier, R., Uhlmann, J.: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. Eur. J. Oper. Res.\u00a0186(2), 542\u2013553 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"33_CR17","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR18","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Treewidth reduction for constrained separation and bipartization problems. In: Marion, J.-Y., Schwentick, T. (eds.) STACS 2010, pp. 561\u2013572 (2010)"},{"key":"33_CR19","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. CoRR, arXiv:1110.4765 (2011)"},{"issue":"20","key":"33_CR20","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1016\/j.ipl.2009.07.016","volume":"109","author":"D. Marx","year":"2009","unstructured":"Marx, D., Razgon, I.: Constant ratio fixed-parameter approximation of the edge multicut problem. Inform. Process. Lett.\u00a0109(20), 1161\u20131166 (2009)","journal-title":"Inform. Process. Lett."},{"key":"33_CR21","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Fortnow, L., Vadhan, S.P. (eds.) STOC 2011, pp. 469\u2013478. ACM (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"33_CR22","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R.E. Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Decomposition by clique separators. Discrete Math.\u00a055, 221\u2013232 (1985)","journal-title":"Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34611-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T05:56:17Z","timestamp":1557294977000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}