{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T02:50:33Z","timestamp":1767495033563},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540220671"},{"type":"electronic","value":"9783540248385"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24838-5_7","type":"book-chapter","created":{"date-parts":[[2010,8,8]],"date-time":"2010-08-08T21:34:14Z","timestamp":1281303254000},"page":"87-99","source":"Crossref","is-referenced-by-count":5,"title":["Simple Max-Cut for Split-Indifference Graphs and Graphs with Few P 4\u2019s"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Celina M. H.","family":"de Figueiredo","sequence":"additional","affiliation":[]},{"given":"Marisa","family":"Gutierrez","sequence":"additional","affiliation":[]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(88)90144-5","volume":"26","author":"C. Arbib","year":"1987","unstructured":"Arbib, C.: A polynomial characterization of some graph partitioning problem. Inform. Process. Lett.\u00a026, 223\u2013230 (1987\/1988)","journal-title":"Inform. Process. Lett."},{"key":"7_CR2","unstructured":"Babel, L.: On the P4-structure of graphs, Habilitationsschrift, Zentrum f\u00fcr Mathematik, Technische Universit\u00e4t M\u00fcnchen (1997)"},{"key":"7_CR3","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0012-365X(00)00258-2","volume":"235","author":"L. Babel","year":"2001","unstructured":"Babel, L., Kloks, T., Kratochv\u00edl, J., Kratsch, D., M\u00fcller, H., Olariu, S.: Efficient algorithms for graphs with few P4\u2019s. Combinatorics (Prague, 1998). Discrete Math.\u00a0235, 29\u201351 (2001)","journal-title":"Combinatorics (Prague, 1998). Discrete Math."},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-218X(97)90120-7","volume":"84","author":"L. Babel","year":"1998","unstructured":"Babel, L., Olariu, S.: On the structure of graphs with few P4s. Discrete Appl. Math.\u00a084, 1\u201313 (1998)","journal-title":"Discrete Appl. Math."},{"key":"7_CR5","unstructured":"Baumann, S.: A linear algorithm for the homogeneous decomposition of graphs, Report No. M-9615, Zentrum f\u00fcr Mathematik, Technische Universit\u00e4t M\u00fcnchen (1996)"},{"key":"7_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1007\/3-540-57785-8_189","volume-title":"STACS 94","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Jansen, K.: On the complexity of the maximum cut problem. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol.\u00a0775, pp. 769\u2013780. Springer, Heidelberg (1994); Also in Nordic J. Comput. 7(1),14\u201331 (2000)"},{"key":"#cr-split#-7_CR7.1","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Kloks, T., Niedermeier, R.: Simple max-cut for unit interval graphs and graphs with few P4???s. In: Extended abstracts of the 6th Twente Workshop on Graphs and Combinatorial Optimization, pp. 12???19 (1999);","DOI":"10.1016\/S1571-0653(05)80014-9"},{"key":"#cr-split#-7_CR7.2","unstructured":"Also in Electronic Notes in Discrete Mathematics 3 (1999)"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0012-365X(98)00310-0","volume":"201","author":"K.P. Bogart","year":"1999","unstructured":"Bogart, K.P., West, D.B.: A short proof that \u2018proper = unit\u2019. Discrete Math.\u00a0201, 21\u201323 (1999)","journal-title":"Discrete Math."},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0020-0190(95)00133-W","volume":"56","author":"C.M.H. Figueiredo de","year":"1995","unstructured":"de Figueiredo, C.M.H., Meidanis, J., de Mello, C.P.: A linear-time algorithm for proper interval graph recognition. Inform. Process. Lett.\u00a056, 179\u2013184 (1995)","journal-title":"Inform. Process. Lett."},{"key":"7_CR11","first-page":"104","volume-title":"RECOMB 2003","author":"E. Eskin","year":"2003","unstructured":"Eskin, E., Halperin, E., Karp, R.M.: Large scale reconstruction of haplotypes from genotype data. In: RECOMB 2003, pp. 104\u2013113. ACM Press, New York (2003)"},{"key":"7_CR12","doi-asserted-by":"crossref","first-page":"17","DOI":"10.46298\/dmtcs.232","volume":"1","author":"V. Giakoumakis","year":"1997","unstructured":"Giakoumakis, V., Roussel, F., Thuillier, H.: On P4-tidy graphs. Discrete Mathematics and Theoretical Computer Science\u00a01, 17\u201341 (1997)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM\u00a042, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"7_CR14","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"issue":"2","key":"7_CR15","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0166-218X(02)00402-X","volume":"130","author":"J. Gramm","year":"2003","unstructured":"Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: Worst-case upper bounds for MAX-2-SAT with application to MAX-CUT. Discrete Appl. Math.\u00a0130(2), 139\u2013155 (2003)","journal-title":"Discrete Appl. Math."},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/0204019","volume":"4","author":"F.O. Hadlock","year":"1975","unstructured":"Hadlock, F.O.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comput.\u00a04, 221\u2013225 (1975)","journal-title":"SIAM J. Comput."},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(92)90036-A","volume":"35","author":"B. Jamison","year":"1992","unstructured":"Jamison, B., Olariu, S.: A tree representation for P4-sparse graphs. Discrete Appl. Math.\u00a035, 115\u2013129 (1992)","journal-title":"Discrete Appl. Math."},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1137\/0221027","volume":"21","author":"B. Jamison","year":"1992","unstructured":"Jamison, B., Olariu, S.: Recognizing P4-sparse graphs in linear time. SIAM J. Comput.\u00a021, 381\u2013406 (1992)","journal-title":"SIAM J. Comput."},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0166-218X(94)00012-3","volume":"61","author":"B. Jamison","year":"1995","unstructured":"Jamison, B., Olariu, S.: Linear time optimization algorithms for P4-sparse graphs. Discrete Appl. Math.\u00a061, 155\u2013175 (1995)","journal-title":"Discrete Appl. Math."},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/S0895480191196812","volume":"8","author":"B. Jamison","year":"1995","unstructured":"Jamison, B., Olariu, S.: p-components and the homogeneous decomposition of graphs. SIAM J. Discrete Math.\u00a08, 448\u2013463 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"7_CR21","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thather, J.W. (eds.) Complexity of computation, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"#cr-split#-7_CR22.1","doi-asserted-by":"crossref","unstructured":"Kloks, T., Tan, R.B.: Bandwidth and topological bandwidth of graphs with few P4???s. In: 1st Japanese-Hungarian Symposium for Discrete Mathematics and its Applications, Kyoto, pp. 117???133 (1999);","DOI":"10.1016\/S0166-218X(01)00220-7"},{"key":"#cr-split#-7_CR22.2","doi-asserted-by":"crossref","unstructured":"Discrete Appl. Math. 115(1-3), 117???133 (2001)","DOI":"10.1016\/S0166-218X(01)00220-7"},{"key":"7_CR23","unstructured":"McKee, T.A., Morris, F.R.: Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1999)"},{"key":"7_CR24","first-page":"502","volume":"10","author":"G.I. Orlova","year":"1972","unstructured":"Orlova, G.I., Dorfman, Y.G.: Finding the maximal cut in a graph. Engrg. Cybernetics\u00a010, 502\u2013504 (1972)","journal-title":"Engrg. Cybernetics"},{"issue":"1-3","key":"7_CR25","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0166-218X(97)00128-5","volume":"82","author":"C. Ortiz","year":"1998","unstructured":"Ortiz, C., Maculan, Z.N., Szwarcfiter, J.L.: Characterizing and edge-colouring split-indifference graphs. Discrete Appl. Math.\u00a082(1-3), 209\u2013217 (1998)","journal-title":"Discrete Appl. Math."},{"key":"7_CR26","doi-asserted-by":"crossref","unstructured":"Poljak, S., Tuza, Z.: Maximum cuts and large bipartite subgraphs. In: Cook, W., Lov\u00e1sz, L., Seymour, P. (eds.) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Providence, RI. Amer. Math. Soc., vol.\u00a020, pp. 181\u2013244 (1995)","DOI":"10.1090\/dimacs\/020\/04"},{"key":"7_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/3-540-45784-4_3","volume-title":"Algorithms in Bioinformatics","author":"R. Rizzi","year":"2002","unstructured":"Rizzi, R., Bafna, V., Istrail, S., Lancia, G.: Practical algorithms and fixedparameter tractability for the single individual SNP haplotypying problem. In: Guig\u00f3, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol.\u00a02452, pp. 29\u201343. Springer, Heidelberg (2002)"},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/0095-8956(71)90010-4","volume":"11","author":"F.S. Roberts","year":"1971","unstructured":"Roberts, F.S.: On the compatibility between a graph and a simple order. J. Combinatorial Theory Ser. B\u00a011, 28\u201338 (1971)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"7_CR29","unstructured":"Wimer, T.V.: Linear algorithms on k-terminal graphs, PhD Thesis, Department of Computer Science, Clemson University, South Carolina (1987)"}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24838-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,4]],"date-time":"2021-11-04T02:09:22Z","timestamp":1635991762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24838-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540220671","9783540248385"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24838-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}