{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:26:54Z","timestamp":1740122814338,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T00:00:00Z","timestamp":1700006400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T00:00:00Z","timestamp":1700006400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100004040","name":"KU Leuven","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004040","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Fonds Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["S007318N"],"award-info":[{"award-number":["S007318N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002913","name":"Vlaamse Overheid","doi-asserted-by":"publisher","award":["Onderzoeksprogramma Artifici\u00eble Intelligentie (AI) Vlaanderen"],"award-info":[{"award-number":["Onderzoeksprogramma Artifici\u00eble Intelligentie (AI) Vlaanderen"]}],"id":[{"id":"10.13039\/501100002913","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2024,4]]},"DOI":"10.1007\/s10732-023-09522-x","type":"journal-article","created":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T19:02:24Z","timestamp":1700074944000},"page":"67-107","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A heuristic algorithm using tree decompositions for the maximum happy vertices problem"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3679-8873","authenticated-orcid":false,"given":"Louis","family":"Carpentier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5256-1921","authenticated-orcid":false,"given":"Jorik","family":"Jooken","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8984-2463","authenticated-orcid":false,"given":"Jan","family":"Goedgebeur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,11,15]]},"reference":[{"key":"9522_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, A.: On the parameterized complexity of happy vertex coloring. In: International Workshop on Combinatorial Algorithms, Springer, pp. 103\u2013115 (2017)","DOI":"10.1007\/978-3-319-78825-8_9"},{"key":"9522_CR2","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.tcs.2020.06.002","volume":"835","author":"A Agrawal","year":"2020","unstructured":"Agrawal, A., Aravind, N., Kalyanasundaram, S., et al.: Parameterized complexity of happy coloring problems. Theoret. Comput. Sci. 835, 58\u201381 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"9522_CR3","doi-asserted-by":"crossref","unstructured":"Aravind, N., Kalyanasundaram, S., Kare, A.S.: Linear time algorithms for happy vertex coloring problems for trees. In: International Workshop on Combinatorial Algorithms, Springer, pp. 281\u2013292 (2016)","DOI":"10.1007\/978-3-319-44543-4_22"},{"issue":"2","key":"9522_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Disc. Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Disc. Methods"},{"issue":"1","key":"9522_CR5","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM (JACM) 41(1), 153\u2013180 (1994)","journal-title":"J. ACM (JACM)"},{"issue":"8","key":"9522_CR6","doi-asserted-by":"publisher","first-page":"172","DOI":"10.3390\/a12080172","volume":"12","author":"M Bannach","year":"2019","unstructured":"Bannach, M., Berndt, S.: Practical access to dynamic programming on tree decompositions. Algorithms 12(8), 172 (2019)","journal-title":"Algorithms"},{"key":"9522_CR7","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.cor.2015.10.014","volume":"68","author":"C Blum","year":"2016","unstructured":"Blum, C., Pinacho, P., L\u00f3pez-Ib\u00e1\u00f1ez, M., et al.: Construct, merge, solve & adapt a new general algorithm for combinatorial optimization. Comput. Oper. Res. 68, 75\u201388 (2016)","journal-title":"Comput. Oper. Res."},{"key":"9522_CR8","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Bonsma, P., Lokshtanov, D.: The fine details of fast dynamic programming over tree decompositions. In: International Symposium on Parameterized and Exact Computation, Springer, pp. 41\u201353 (2013)","DOI":"10.1007\/978-3-319-03898-8_5"},{"issue":"2","key":"9522_CR9","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., et al.: A c$$^\\text{ k }n$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"key":"9522_CR10","unstructured":"Carpentier, L.: Developing heuristic algorithms for graph optimisation problems using tree decompositions. Master\u2019s thesis (Supervisors: Prof. Jan Goedgebeur and Jorik Jooken), KU Leuven. Faculteit Ingenieurswetenschappen (2022)"},{"key":"9522_CR11","doi-asserted-by":"crossref","unstructured":"Coolsaet, K., D\u2019hondt, S., Goedgebeur, J.: House of graphs 2.0: A database of interesting graphs and more. Discrete Appl. Math. 325, 97\u2013107 (2023)","DOI":"10.1016\/j.dam.2022.10.013"},{"key":"9522_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, et al.: Parameterized Algorithms, vol. 5. Springer, Cham, Switzerland (2015)"},{"key":"9522_CR13","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., et\u00a0al.: The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"9522_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942","volume-title":"Networks, Crowds, and Markets: Reasoning About a Highly Connected World","author":"D Easley","year":"2010","unstructured":"Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, New York, NY (2010)"},{"issue":"1","key":"9522_CR15","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5(1), 17\u201360 (1960)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"9522_CR16","doi-asserted-by":"crossref","unstructured":"Gao, H., Gao, W.: Kernelization for maximum happy vertices problem. In: Latin American Symposium on Theoretical Informatics, Springer, pp. 504\u2013514 (2018)","DOI":"10.1007\/978-3-319-77404-6_37"},{"issue":"1","key":"9522_CR17","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s11750-021-00610-4","volume":"30","author":"M Ghirardi","year":"2022","unstructured":"Ghirardi, M., Salassa, F.: A simple and effective algorithm for the maximum happy vertices problem. TOP 30(1), 181\u2013193 (2022)","journal-title":"TOP"},{"key":"9522_CR18","first-page":"1","volume":"23","author":"M Hamann","year":"2018","unstructured":"Hamann, M., Strasser, B.: Graph bisection with pareto optimization. J. Exp. Algorithmics (JEA) 23, 1\u201334 (2018)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"9522_CR19","doi-asserted-by":"crossref","unstructured":"Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: International conference on learning and intelligent optimization, Springer, pp. 507\u2013523 (2011)","DOI":"10.1007\/978-3-642-25566-3_40"},{"issue":"5","key":"9522_CR20","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/s10732-020-09447-9","volume":"26","author":"J Jooken","year":"2020","unstructured":"Jooken, J., Leyman, P., De Causmaecker, P.: A multi-start local search algorithm for the hamiltonian completion problem on undirected graphs. Journal of Heuristics 26(5), 743\u2013769 (2020)","journal-title":"Journal of Heuristics"},{"key":"9522_CR21","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. Springer (2010)"},{"key":"9522_CR22","first-page":"116","volume":"38","author":"D K\u0151nig","year":"1931","unstructured":"K\u0151nig, D.: Gr\u00e1fok \u00e9s m\u00e1trixok. Matematikai \u00e9s Fizikai Lapok 38, 116\u2013119 (1931)","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"9522_CR23","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.cor.2018.11.015","volume":"103","author":"R Lewis","year":"2019","unstructured":"Lewis, R., Thiruvady, D., Morgan, K.: Finding happiness: an analysis of the maximum happy vertices problem. Comput. Oper. Res. 103, 265\u2013276 (2019)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"9522_CR24","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory, Series B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theory, Series B"},{"key":"9522_CR25","unstructured":"Peeters, F.: Oplossingsmethodes voor het maximum happy vertices probleem. Master\u2019s thesis (Supervisor: Prof. Patrick De Causmaecker), KU Leuven. Faculteit Ingenieurswetenschappen (2020)"},{"issue":"1","key":"9522_CR26","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory, Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"9522_CR27","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s10878-018-0353-z","volume":"37","author":"H Tamaki","year":"2019","unstructured":"Tamaki, H.: Positive-instance driven dynamic programming for treewidth. J. Comb. Optim. 37(4), 1283\u20131311 (2019)","journal-title":"J. Comb. Optim."},{"key":"9522_CR28","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s10288-020-00431-4","volume":"18","author":"D Thiruvady","year":"2020","unstructured":"Thiruvady, D., Lewis, R., Morgan, K.: Tackling the maximum happy vertices problem in large networks. 4OR 18, 507\u2013527 (2020)","journal-title":"4OR"},{"key":"9522_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2015.06.003","volume":"593","author":"P Zhang","year":"2015","unstructured":"Zhang, P., Li, A.: Algorithmic aspects of homophyly of networks. Theoret. Comput. Sci. 593, 117\u2013131 (2015)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-023-09522-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-023-09522-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-023-09522-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T08:46:47Z","timestamp":1710406007000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-023-09522-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,15]]},"references-count":29,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["9522"],"URL":"https:\/\/doi.org\/10.1007\/s10732-023-09522-x","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"type":"print","value":"1381-1231"},{"type":"electronic","value":"1572-9397"}],"subject":[],"published":{"date-parts":[[2023,11,15]]},"assertion":[{"value":"24 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"not applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"not applicable","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}