{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T02:47:06Z","timestamp":1767494826963},"reference-count":23,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[1999,5,1]],"date-time":"1999-05-01T00:00:00Z","timestamp":925516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[1999,5]]},"DOI":"10.1016\/s1571-0653(05)80014-9","type":"journal-article","created":{"date-parts":[[2005,4,30]],"date-time":"2005-04-30T07:22:13Z","timestamp":1114845733000},"page":"19-26","source":"Crossref","is-referenced-by-count":9,"special_numbering":"C","title":["SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s"],"prefix":"10.1016","volume":"3","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(05)80014-9_BIB1","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(88)90144-5","article-title":"A polynomial characterization of some graph partitioning problem","volume":"26","author":"Arbib","year":"1987","journal-title":"Information Processing Letters"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB2","series-title":"Habilitationsschrift","article-title":"On the P4-structure of graphs","author":"Babel","year":"1997"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB3","unstructured":"Babel, L., T. Kloks, J. Kratochv\u00ecl, D. Kratsch, H. M\u00fcller, and S. Olariu, Efficient algorithms for graphs with few P4s. Manuscript 1999."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB4","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":"10.1016\/S1571-0653(05)80014-9_BIB5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H. and K. Jansen, On the complexity of the Maximum Cut problem, Proc. STACS94, Springer-Verlag, Lecture Notes in Computer Science 775, (1994), pp. 769-780.","DOI":"10.1007\/3-540-57785-8_189"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB6","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0012-365X(98)00310-0","article-title":"A short proof that \u2018proper = unit\u2019","volume":"201","author":"Bogart","year":"1999","journal-title":"Discrete Mathematics"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB7","unstructured":"Brandst\u00e4dt, A., Special graph classes - A survey, Schriftenreihe des Fachbereichs Mathematik, SM-DU-199 (1991), Universit\u00e4t Duisburg Gesamthochschule."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB9","doi-asserted-by":"crossref","first-page":"17","DOI":"10.46298\/dmtcs.232","article-title":"On P4-tidy graphs","volume":"1","author":"Giakoumakis","year":"1997","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB10","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","article-title":"A characterization of comparability and interval graphs","volume":"16","author":"Gilmore","year":"1964","journal-title":"Canad. J. Math."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB11","series-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic","year":"1980"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","article-title":"Finding a maximum cut of a planar graph in polynomial time","volume":"4","author":"Hadlock","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB13","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0166-218X(91)90085-B","article-title":"On a tree representation for P4-extendible graph","volume":"34","author":"Jamison","year":"1991","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0166-218X(92)90036-A","article-title":"A tree representation for P4-sparse graphs","volume":"35","author":"Jamison","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB15","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1137\/0221027","article-title":"Recognizing P4-sparse graphs in linear time","volume":"21","author":"Jamison","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB16","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0166-218X(94)00012-3","article-title":"Linear time optimization algorithms for P4-sparse graphs","volume":"61","author":"Jamison","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB17","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1137\/S0895480191196812","article-title":"P-components and the homogeneous decomposition of graphs","volume":"8","author":"Jamison","year":"1995","journal-title":"SIAM J. Discrete Mathematics"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB18","series-title":"Complexity of computation","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB19","unstructured":"Kloks, T. and R. B. Tan, Bandwidth and topological bandwidth of graphs with few P4s, Technical report WS-511, November 1998, Department of Computer Science, Vrije Universiteit Amsterdam."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB20","first-page":"502","article-title":"Finding the maximal cut in a graph","volume":"10","author":"Orlova","year":"1972","journal-title":"Engrg. Cybernetics"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB21","first-page":"181","article-title":"Maximum cuts and large bipartite subgraphs","volume":"20","author":"Poljak","year":"1995"},{"key":"10.1016\/S1571-0653(05)80014-9_BIB22","unstructured":"Wimer, T. V., Linear algorithms on k-terminal graphs, PhD Thesis, Department of Computer Science, Clemson University, South Carolina, 1987."},{"key":"10.1016\/S1571-0653(05)80014-9_BIB23","doi-asserted-by":"crossref","unstructured":"Yannakakis, M., Node-deletion NP-complete problems, Proc. 10th Ann. A.C.M. Symp. on Theory of Comp., (1978), pp. 253-264.","DOI":"10.1145\/800133.804355"}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065305800149?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065305800149?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T23:48:13Z","timestamp":1683071293000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065305800149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,5]]},"references-count":23,"alternative-id":["S1571065305800149"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(05)80014-9","relation":{},"ISSN":["1571-0653"],"issn-type":[{"value":"1571-0653","type":"print"}],"subject":[],"published":{"date-parts":[[1999,5]]}}}