{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:29Z","timestamp":1740109589927,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T00:00:00Z","timestamp":1682985600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T00:00:00Z","timestamp":1682985600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["303803\/2020-7","407635\/2018-1","140399\/2017-8"],"award-info":[{"award-number":["303803\/2020-7","407635\/2018-1","140399\/2017-8"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005283","name":"Funda\u00e7\u00e3o Cearense de Apoio ao Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["PNE-0112-00061.01.00\/16"],"award-info":[{"award-number":["PNE-0112-00061.01.00\/16"]}],"id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro","doi-asserted-by":"publisher","award":["E-26\/202.793\/2017"],"award-info":[{"award-number":["E-26\/202.793\/2017"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["Finance code 001"],"award-info":[{"award-number":["Finance code 001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s00454-023-00508-x","type":"journal-article","created":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T14:52:55Z","timestamp":1683039175000},"page":"893-917","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete"],"prefix":"10.1007","volume":"71","author":[{"given":"Celina M. H.","family":"de Figueiredo","sequence":"first","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Alexsander A.","family":"de Melo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"given":"Fabiano S.","family":"Oliveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8917-0564","authenticated-orcid":false,"given":"Ana","family":"Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocab":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,2]]},"reference":[{"key":"508_CR1","unstructured":"Adhikary, R., Bose, K., Mukherjee, S., Roy, B.: Complexity of maximum cut on interval graphs. In: 37th International Symposium on Computational Geometry. Leibniz Int. Proc. Inform., vol. 189, #\u00a07. Leibniz-Zent. Inform., Wadern (2021)"},{"key":"508_CR2","doi-asserted-by":"crossref","unstructured":"Berman, P., Karpinski, M.: On some tighter inapproximability results. In: Automata, Languages and Programming (Prague 1999). Lecture Notes in Computer Science, vol. 1644, pp. 200\u2013209. Springer, Berlin (1999)","DOI":"10.1007\/3-540-48523-6_17"},{"key":"508_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., de Figueiredo, C.M.H., Gutierrez, M., Kloks, T., Niedermeier, R.: Simple max-cut for split-indifference graphs and graphs with few $$P_4$$\u2019s. In: 3rd International Workshop on Experimental and Efficient Algorithms (Angra dos Reis 2004). Lecture Notes in Computer Science, vol. 3059, pp. 87\u201399. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24838-5_7"},{"key":"508_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Kloks, T., Niedermeier, R.: Simple max-cut for unit interval graphs and graphs with few $$P_4$$s. In: 6th Twente Workshop on Graphs and Combinatorial Optimization (Enschede 1999). Electronic Notes in Discrete Mathematics, vol. 3, pp. 19\u201326. Elsevier, Amsterdam (1999)","DOI":"10.1016\/S1571-0653(05)80014-9"},{"key":"508_CR5","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics, vol. 244. Springer, New York (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"508_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.ipl.2017.01.007","volume":"121","author":"A Boyac\u0131","year":"2017","unstructured":"Boyac\u0131, A., Ekim, T., Shalom, M.: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Inform. Process. Lett. 121, 29\u201333 (2017)","journal-title":"Inform. Process. Lett."},{"issue":"7","key":"508_CR7","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1016\/j.dam.2010.07.006","volume":"159","author":"MR Cerioli","year":"2011","unstructured":"Cerioli, M.R., de Oliveira, F.S., Szwarcfiter, J.L.: On counting interval lengths of interval graphs. Discrete Appl. Math. 159(7), 532\u2013543 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"508_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s13173-011-0047-1","volume":"18","author":"MR Cerioli","year":"2012","unstructured":"Cerioli, M.R., de Oliveira, F.S., Szwarcfiter, J.L.: The interval count of interval graphs and orders: a short survey. J. Braz. Comput. Soc. 18(2), 103\u2013112 (2012)","journal-title":"J. Braz. Comput. Soc."},{"key":"508_CR9","unstructured":"Chakraborty, D., Das, S., Foucaud, F., Gahlawat, H., Lajou, D., Roy, B.: Algorithms and complexity for geodetic sets on planar and chordal graphs. In: 31st International Symposium on Algorithms and Computation. Leibniz Int. Proc. Inform., vol. 181, #\u00a07. Leibniz-Zent. Inform., Wadern (2020)"},{"key":"508_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, J., Fomin, F., Heggernes, P., Kratsch, D., Kucherov, G.: Optimal linear arrangement of interval graphs. In: International Symposium on Mathematical Foundations of Computer Science (Star\u00e1 Lesn\u00e1 2006). Lecture Notes in Computer Science, vol. 4162, pp. 267\u2013279. Springer, Berlin (2006)","DOI":"10.1007\/11821069_24"},{"issue":"2","key":"508_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"DG Corneil","year":"1995","unstructured":"Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Inform. Process. Lett. 55(2), 99\u2013104 (1995)","journal-title":"Inform. Process. Lett."},{"key":"508_CR12","doi-asserted-by":"crossref","unstructured":"Ekim, T., Erey, A., Heggernes, P., van \u2019t Hof, P., Meister, D.: Computing minimum geodetic sets of proper interval graphs. LATIN 2012: Theoretical Informatics (Arequipa 2012). Lecture Notes in Computer Science, vol. 7256, pp. 279\u2013290. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-29344-3_24"},{"key":"508_CR13","unstructured":"de Figueiredo, C.M.H., de Melo, A.A., Oliveira, F.S., Silva, A.: Maximum cut on interval graphs of interval count five is NP-complete (2020). arXiv:2012.09804"},{"key":"508_CR14","unstructured":"de Figueiredo, C.M.H., de Melo, A.A., Oliveira, F.S., Silva, A.: Maximum cut on interval graphs of interval count four is NP-complete. In: 46th International Symposium on Mathematical Foundations of Computer Science (Tallinn 2021). Leibniz Int. Proc. Inform., vol. 202, #\u00a038. Leibniz-Zent. Inform., Wadern (2021)"},{"key":"508_CR15","doi-asserted-by":"crossref","unstructured":"de Figueiredo, C.M.H., de Melo, A.A., Sasaki, D., Silva, A.: Revising Johnson\u2019s table for the 21st century. Discrete Appl. Math. 323, 184\u2013200 (2022)","DOI":"10.1016\/j.dam.2021.05.021"},{"issue":"2","key":"508_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(85)90042-1","volume":"55","author":"PC Fishburn","year":"1985","unstructured":"Fishburn, P.C.: Interval graphs and interval orders. Discrete Math. 55(2), 135\u2013149 (1985)","journal-title":"Discrete Math."},{"issue":"3","key":"508_CR17","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified $${N\\!P}$$-complete problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"508_CR18","doi-asserted-by":"crossref","unstructured":"Herrera de Figueiredo, C.M., Meidanis, J., Picinin de Mello,\u00a0C.: A linear-time algorithm for proper interval graph recognition. Inform. Process. Lett. 56(3), 179\u2013184 (1995)","DOI":"10.1016\/0020-0190(95)00133-W"},{"issue":"3","key":"508_CR19","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"DS Johnson","year":"1985","unstructured":"Johnson, D.S.: The NP-completeness column: an ongoing guide. J. Algorithms 6(3), 434\u2013451 (1985)","journal-title":"J. Algorithms"},{"issue":"4","key":"508_CR20","doi-asserted-by":"publisher","first-page":"1490","DOI":"10.1007\/s00453-018-0481-y","volume":"81","author":"P Klav\u00edk","year":"2019","unstructured":"Klav\u00edk, P., Otachi, Y., \u0160ejnoha, J.: On the classes of interval graphs of limited nesting and count of lengths. Algorithmica 81(4), 1490\u20131511 (2019)","journal-title":"Algorithmica"},{"key":"508_CR21","unstructured":"Kratochv\u00edl, J., Masa\u0159\u00edk, T., Novotn\u00e1, J.: $$\\cal{U}$$-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited. In: 45th International Symposium on Mathematical Foundations of Computer Science. Leibniz Int. Proc. Inform., vol. 170, #\u00a057. Leibniz-Zent. Inform., Wadern (2020)"},{"issue":"4","key":"508_CR22","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.orl.2004.07.006","volume":"33","author":"D Marx","year":"2005","unstructured":"Marx, D.: A short proof of the NP-completeness of minimum sum interval coloring. Oper. Res. Lett. 33(4), 382\u2013384 (2005)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"508_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/PL00009252","volume":"23","author":"S Nicoloso","year":"1999","unstructured":"Nicoloso, S., Sarrafzadeh, M., Song, X.: On the sum coloring problem on interval graphs. Algorithmica 23(2), 109\u2013126 (1999)","journal-title":"Algorithmica"},{"key":"508_CR24","unstructured":"Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory (Ann Arbor 1968), pp. 139\u2013146. Academic Press, New York (1969)"},{"key":"508_CR25","doi-asserted-by":"crossref","unstructured":"Yuan, J., Zhou, S.: Optimal labelling of unit interval graphs. Appl. Math. J. Chin. Univ. Ser. B 10(3), 337\u2013344 (1995)","DOI":"10.1007\/BF02662875"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00508-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00508-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00508-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,11]],"date-time":"2024-03-11T15:11:16Z","timestamp":1710169876000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00508-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,2]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["508"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00508-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,5,2]]},"assertion":[{"value":"17 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}