{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T04:44:04Z","timestamp":1770439444644,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,1,16]],"date-time":"2014-01-16T00:00:00Z","timestamp":1389830400000},"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":[[2015,7]]},"DOI":"10.1007\/s00453-014-9868-6","type":"journal-article","created":{"date-parts":[[2014,1,15]],"date-time":"2014-01-15T12:58:42Z","timestamp":1389790722000},"page":"687-713","source":"Crossref","is-referenced-by-count":3,"title":["On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties"],"prefix":"10.1007","volume":"72","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yngve","family":"Villanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,1,16]]},"reference":[{"key":"9868_CR1","doi-asserted-by":"crossref","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 42, 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"9868_CR2","doi-asserted-by":"crossref","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. 75, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9868_CR3","first-page":"629","volume-title":"FOCS 2009","author":"H.L. Bodlaender","year":"2009","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, Los Alamitos (2009)"},{"issue":"35","key":"9868_CR4","doi-asserted-by":"crossref","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. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"35","key":"9868_CR5","doi-asserted-by":"crossref","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. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9868_CR6","first-page":"459","volume-title":"STOC 2011","author":"N. Bousquet","year":"2011","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: Fortnow, L., Vadhan, S.P. (eds.) STOC 2011, pp. 459\u2013468. ACM, New York (2011)"},{"issue":"1","key":"9868_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J. Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica 55(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"key":"9868_CR8","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, J. (ed.) Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, pp. 193\u2013242. Elsevier\/MIT Press, Amsterdam (1990)"},{"key":"9868_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1007\/978-3-642-04128-0_64","volume-title":"ESA 2009","author":"E. Demaine","year":"2009","unstructured":"Demaine, E., Hajiaghayi, M., Marx, D.: Minimizing movement: fixed-parameter tractability. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 718\u2013729. Springer, Berlin (2009)"},{"key":"9868_CR10","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, Electronic edn. (2005)"},{"key":"9868_CR11","series-title":"Monographs in Computer Science","doi-asserted-by":"crossref","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":"9868_CR12","doi-asserted-by":"crossref","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 1, 195\u2013207 (1971)","journal-title":"Networks"},{"key":"9868_CR13","first-page":"375","volume-title":"STOC 2006","author":"U. Feige","year":"2006","unstructured":"Feige, U., Mahdian, M.: Finding small balanced separators. In: Kleinberg, J.M. (ed.) STOC 2006, pp.\u00a0375\u2013384. ACM, New York (2006)"},{"key":"9868_CR14","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410, 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9868_CR15","first-page":"503","volume-title":"SODA 2010","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Charikar, M. (ed.) SODA 2010, pp. 503\u2013510. SIAM, Philadelphia (2010)"},{"key":"9868_CR16","doi-asserted-by":"crossref","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. 77, 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9868_CR17","doi-asserted-by":"crossref","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. Inf. Process. Lett. 103(4), 136\u2013141 (2007)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9868_CR18","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.disopt.2010.05.003","volume":"8","author":"S. Guillemot","year":"2011","unstructured":"Guillemot, S.: FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optim. 8(1), 61\u201371 (2011)","journal-title":"Discrete Optim."},{"issue":"2","key":"9868_CR19","doi-asserted-by":"crossref","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. 186(2), 542\u2013553 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"9868_CR20","series-title":"LNCS","first-page":"332","volume-title":"WG 2012","author":"P. Heggernes","year":"2012","unstructured":"Heggernes, P., van \u2019t Hof, P., Marx, D., Misra, N., Villanger, Y.: On the parameterized complexity of finding separators with non-hereditary properties. In: Golumbic, M.C., Stern, M. (eds.) WG 2012. LNCS, vol.\u00a07551, pp.\u00a0332\u2013343. Springer, Berlin (2012)"},{"key":"9868_CR21","volume-title":"Annals of Discrete Mathematics","author":"F.K. Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: Steiner tree problems. In: Annals of Discrete Mathematics, vol. 53. North-Holland, Amsterdam (1992)"},{"key":"9868_CR22","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum, New York (1972)"},{"issue":"3","key":"9868_CR23","doi-asserted-by":"crossref","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. 351(3), 394\u2013406 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"20","key":"9868_CR24","doi-asserted-by":"crossref","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. Inf. Process. Lett. 109(20), 1161\u20131166 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9868_CR25","first-page":"469","volume-title":"STOC 2011","author":"D. Marx","year":"2011","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, New York (2011)"},{"key":"9868_CR26","first-page":"561","volume-title":"STACS 2010","author":"D. Marx","year":"2010","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)"},{"issue":"4","key":"9868_CR27","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/2500119","volume":"9","author":"D. Marx","year":"2013","unstructured":"Marx, D., O\u2019Sullivan, B., Razgon, I.: Finding small separators in linear time via treewidth reduction. ACM Trans. Algorithms 9(4), 30 (2013)","journal-title":"ACM Trans. Algorithms"},{"key":"9868_CR28","doi-asserted-by":"crossref","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. 55, 221\u2013232 (1985)","journal-title":"Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9868-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9868-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9868-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T11:58:21Z","timestamp":1565092701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9868-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,16]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["9868"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9868-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1,16]]}}}