{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T15:43:46Z","timestamp":1725637426659},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642258695"},{"type":"electronic","value":"9783642258701"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25870-1_2","type":"book-chapter","created":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T13:32:45Z","timestamp":1322659965000},"page":"5-10","source":"Crossref","is-referenced-by-count":35,"title":["Important Separators and Parameterized Algorithms"],"prefix":"10.1007","author":[{"given":"D\u00e1niel","family":"Marx","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Daligault, J., Thomass\u00e9, S.: Multicut is FPT. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 459\u2013468 (2011)","DOI":"10.1145\/1993636.1993698"},{"key":"2_CR2","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":"2_CR3","doi-asserted-by":"crossref","unstructured":"Chen, J., Liu, Y., Lu, S., O\u2019Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM\u00a055(5) (2008)","DOI":"10.1145\/1411509.1411511"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. Accepted to SODA (2012)","DOI":"10.1137\/1.9781611973099.136"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.: On multiway cut parameterized above lower bounds. Accepted to IPEC (2011)","DOI":"10.1007\/978-3-642-28050-4_1"},{"issue":"4","key":"2_CR6","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput.\u00a023(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"2_CR7","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","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. Monographs in Computer Science. Springer, New York (1999)"},{"key":"2_CR8","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"2_CR9","unstructured":"Heggernes, P.: van\u00a0\u2019t Hof, P., Lokshtanov, D., Paul, C.: Obtaining a bipartite graph by contracting few edges. CoRR abs\/1102.5441 (2011)"},{"key":"2_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1007\/978-3-642-22006-7_66","volume-title":"Automata, Languages and Programming","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D.: Clustering with Local Restrictions. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol.\u00a06755, pp. 785\u2013797. Springer, Heidelberg (2011)"},{"issue":"3","key":"2_CR11","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. Theoret. Comput. Sci.\u00a0351(3), 394\u2013406 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proceedings of the 43nd ACM Symposium on Theory of Computing, pp. 469\u2013478 (2011)","DOI":"10.1145\/1993636.1993699"},{"key":"2_CR13","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","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 Lecture Series in Mathematics and its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"issue":"4","key":"2_CR14","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters\u00a032(4), 299\u2013301 (2004)","journal-title":"Operations Research Letters"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-540-79709-8_32","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Xiao","year":"2008","unstructured":"Xiao, M.: Algorithms for Multiterminal Cuts. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) CSR 2008. LNCS, vol.\u00a05010, pp. 314\u2013325. Springer, Heidelberg (2008)"}],"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-25870-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T04:04:44Z","timestamp":1561003484000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25870-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642258695","9783642258701"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25870-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}