{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:12Z","timestamp":1759639092114,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319181721"},{"type":"electronic","value":"9783319181738"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18173-8_21","type":"book-chapter","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T08:47:43Z","timestamp":1431679663000},"page":"288-299","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms Solving the Matching Cut Problem"],"prefix":"10.1007","author":[{"given":"Dieter","family":"Kratsch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters 8, 121\u2013123 (1979). Erratum: 14 (1982) 195","key":"21_CR1","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1002\/jgt.20390","volume":"62","author":"P Bonsma","year":"2009","unstructured":"Bonsma, P.: The complexity of the Matching-Cut problem for planar graphs and other graph classes. J. Graph Theory 62, 109\u2013126 (2009)","journal-title":"J. Graph Theory"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1016\/j.tcs.2008.07.002","volume":"407","author":"M Borowiecki","year":"2008","unstructured":"Borowiecki, M., Jesse-J\u00f3zefczyk, K.: Matching cutsets in graphs of diameter 2. Theoret. Comp. Sci. 407, 574\u2013582 (2008)","journal-title":"Theoret. Comp. Sci."},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0166-218X(00)00197-9","volume":"105","author":"A Brandst\u00e4dt","year":"2000","unstructured":"Brandst\u00e4dt, A., Dragan, F., Le, V.B., Szymczak, T.: On stable cutsets in graphs. Discrete Appl. Math. 105, 39\u201350 (2000)","journal-title":"Discrete Appl. Math."},{"key":"21_CR5","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/PL00021188","volume":"15","author":"Y Caro","year":"1999","unstructured":"Caro, Y., Yuster, R.: Decomposition of slim graphs. Graphs Combinatorics 15, 5\u201319 (1999)","journal-title":"Graphs Combinatorics"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1002\/jgt.10074","volume":"41","author":"G Chen","year":"2002","unstructured":"Chen, G., Faudree, R.J., Jacobson, M.S.: Fragile graphs with small independent cuts. J. Graph Theory 41, 327\u2013341 (2002)","journal-title":"J. Graph Theory"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0012-365X(01)00226-6","volume":"249","author":"G Chen","year":"2002","unstructured":"Chen, G., Xingxing, Y.: A note on fragile graphs. Discrete Math. 249, 41\u201343 (2002)","journal-title":"Discrete Math."},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/jgt.3190080106","volume":"8","author":"V Chv\u00e1tal","year":"1984","unstructured":"Chv\u00e1tal, V.: Recognizing decomposable graphs. J. Graph Theory 8, 51\u201353 (1984)","journal-title":"J. Graph Theory"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jctb.1993.1049","volume":"59","author":"G Derek","year":"1993","unstructured":"Derek, G.: Corneil, Jean Fonlupt, Stable set bonding in perfect graphs and parity graphs. J. Combin. Theory (B) 59, 1\u201314 (1993)","journal-title":"J. Combin. Theory (B)"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. J. ACM 7, 201\u2013215 (1960)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer (2013)","key":"21_CR11","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Computing 5, 691\u2013703 (1976)","journal-title":"SIAM J. Computing"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1002\/net.3230120404","volume":"12","author":"MF Arthur","year":"1982","unstructured":"Arthur, M.F., Proskurowski, A.: Networks immune to isolated line failures. Networks 12, 393\u2013403 (1982)","journal-title":"Networks"},{"unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)","key":"21_CR14"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer (2010)","key":"21_CR15","DOI":"10.1007\/978-3-642-16533-7"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1111\/j.1749-6632.1970.tb56468.x","volume":"175","author":"RL Graham","year":"1970","unstructured":"Graham, R.L.: On primitive graphs and optimal vertex assignments. Ann. N.Y. Acad. Sci. 175, 170\u2013186 (1970)","journal-title":"Ann. N.Y. Acad. Sci."},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63, 512\u2013530 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7, 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"21_CR19","first-page":"217","volume":"119","author":"S Klein","year":"1996","unstructured":"Klein, S., de Figueiredo, C.M.H.: The NP-completeness of multi-partite cutset testing. Congressus Numerantium 119, 217\u2013222 (1996)","journal-title":"Congressus Numerantium"},{"key":"21_CR20","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/j.jda.2007.04.001","volume":"6","author":"VB Le","year":"2008","unstructured":"Le, V.B., Mosca, R., M\u00fcller, H.: On stable cutsets in claw-free graphs and planar graphs. J. Discrete Algorithms 6, 256\u2013276 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"21_CR21","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/S0304-3975(03)00048-3","volume":"301","author":"VB Le","year":"2003","unstructured":"Le, V.B., Randerath, B.: On stable cutsets in line graphs. Theoret. Comput. Sci. 301, 463\u2013475 (2003)","journal-title":"Theoret. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Le, V.B., Pfender, F.: Extremal graphs having no stable cutsets. Electr. J. Comb. 20, #P35 (2013)","key":"21_CR22","DOI":"10.37236\/2513"},{"key":"21_CR23","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1002\/jgt.3190130502","volume":"13","author":"AM Moshi","year":"1989","unstructured":"Moshi, A.M.: Matching cutsets in graphs. J. Graph Theory 13, 527\u2013536 (1989)","journal-title":"J. Graph Theory"},{"doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford University Press (2006)","key":"21_CR24","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/3-540-45477-2_26","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Patrignani","year":"2001","unstructured":"Patrignani, M., Pizzonia, M.: The complexity of the matching-cut problem. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS 2204, vol. 2204, pp. 284\u2013295. Springer, Heidelberg (2001)"},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/0095-8956(83)90039-4","volume":"34","author":"A Tucker","year":"1983","unstructured":"Tucker, A.: Coloring graphs with stable cutsets. J. Combin. Theory (B) 34, 258\u2013267 (1983)","journal-title":"J. Combin. Theory (B)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18173-8_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T08:55:52Z","timestamp":1676451352000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18173-8_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319181721","9783319181738"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18173-8_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 May 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}