{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:54:53Z","timestamp":1740142493769,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T00:00:00Z","timestamp":1694390400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T00:00:00Z","timestamp":1694390400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005012","name":"\u00d6sterreichische Agentur f\u00fcr Internationale Mobilit\u00e4t und Kooperation in Bildung, Wissenschaft und Forschung","doi-asserted-by":"publisher","award":["SI 31\/2020, SI 13\/2023"],"award-info":[{"award-number":["SI 31\/2020, SI 13\/2023"]}],"id":[{"id":"10.13039\/501100005012","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["BI-AT\/20-21-015, BI-AT\/23-24-009","I0-0035, P1-0285, P1-0383, P1-0404, N1-0102, N1-0160, N1-0210, J1-3001, J1-3002, J1-3003, J1-4008, J5-4596"],"award-info":[{"award-number":["BI-AT\/20-21-015, BI-AT\/23-24-009","I0-0035, P1-0285, P1-0383, P1-0404, N1-0102, N1-0160, N1-0210, J1-3001, J1-3002, J1-3003, J1-4008, J5-4596"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008530","name":"European Regional Development Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009057","name":"Karl-Franzens-Universit\u00e4t Graz","doi-asserted-by":"publisher","award":["Field of Excellence \u201cCOLIBRI\u201d"],"award-info":[{"award-number":["Field of Excellence \u201cCOLIBRI\u201d"]}],"id":[{"id":"10.13039\/501100009057","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012416","name":"Bundesministerium f\u00fcr Digitalisierung und Wirtschaftsstandort","doi-asserted-by":"publisher","award":["FIT4BA"],"award-info":[{"award-number":["FIT4BA"]}],"id":[{"id":"10.13039\/501100012416","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009057","name":"University of Graz","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009057","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comp. Appl. Math."],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the fair allocation of indivisible items to several agents with additional conflict constraints. These are represented by a conflict graph where each item corresponds to a vertex of the graph and edges in the graph represent incompatible pairs of items which should not be allocated to the same agent. This setting combines the issues of P<jats:sc>artition<\/jats:sc> and I<jats:sc>ndependent<\/jats:sc> S<jats:sc>et<\/jats:sc> and can be seen as a partial coloring of the conflict graph. In the resulting optimization problem, each agent has its own valuation function for the profits of the items. We aim at maximizing the lowest total profit obtained by any of the agents. In a previous paper, this problem was shown to be strongly -hard for several well-known graph classes, e.g., bipartite graphs and their line graphs. On the other hand, it was shown that pseudo-polynomial time algorithms exist for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. In this contribution, we extend this line of research by developing pseudo-polynomial time algorithms that solve the problem for the class of convex bipartite conflict graphs, graphs of bounded clique-width, and graphs of bounded tree-independence number. The algorithms are based on dynamic programming and also permit fully polynomial-time approximation schemes (FPTAS).<\/jats:p>","DOI":"10.1007\/s40314-023-02437-0","type":"journal-article","created":{"date-parts":[[2023,9,11]],"date-time":"2023-09-11T09:02:00Z","timestamp":1694422920000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fair allocation algorithms for indivisible items under structured conflict constraints"],"prefix":"10.1007","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8169-0925","authenticated-orcid":false,"given":"Nina","family":"Chiarelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4960-8901","authenticated-orcid":false,"given":"Matja\u017e","family":"Krnc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8222-8097","authenticated-orcid":false,"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8881-1497","authenticated-orcid":false,"given":"Ulrich","family":"Pferschy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2268-0612","authenticated-orcid":false,"given":"Joachim","family":"Schauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,11]]},"reference":[{"key":"2437_CR1","doi-asserted-by":"crossref","unstructured":"Bansal N, Sviridenko M (2006) The Santa Claus problem. In: STOC\u201906: proceedings of the 38th Annual ACM symposium on theory of computing. ACM, New York, pp 31\u201340","DOI":"10.1145\/1132516.1132522"},{"issue":"1\u20132","key":"2437_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0012-365X(89)90193-3","volume":"74","author":"C Berge","year":"1989","unstructured":"Berge C (1989) Minimax relations for the partial $$q$$-colorings of a graph. Discret Math 74(1\u20132):3\u201314","journal-title":"Discret Math"},{"key":"2437_CR3","doi-asserted-by":"crossref","unstructured":"Bergougnoux B, Dreier J, Jaffke L (2023) A logic-based algorithmic meta-theorem for MIM-width. In: Proceedings of the 2023 annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM, Philadelphia, PA, pp 3282\u20133304","DOI":"10.1137\/1.9781611977554.ch125"},{"issue":"1\u20133","key":"2437_CR4","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0012-365X(92)90646-W","volume":"100","author":"M B\u00edr\u00f3","year":"1992","unstructured":"B\u00edr\u00f3 M, Hujter M, Tuza Z (1992) Precoloring extension. I. Interval graphs. Discret Math 100(1\u20133):267\u2013279","journal-title":"Discret Math"},{"key":"2437_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender H, Jansen K (1993) On the complexity of scheduling incompatible jobs with unit-times. In: MFCS \u201993: proceedings of the 18th international symposium on mathematical foundations of computer science. Springer, pp 291\u2013300","DOI":"10.1007\/3-540-57182-5_21"},{"key":"2437_CR6","unstructured":"Bodlaender H, Gustedt J, Telle JA (1998) Linear-time register allocation for a fixed number of registers. In: Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms. ACM, New York, pp 574\u2013583"},{"key":"2437_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.dam.2018.03.072","volume":"261","author":"F Bonomo","year":"2019","unstructured":"Bonomo F, de Estrada D (2019) On the thinness and proper thinness of a graph. Discret Appl Math 261:78\u201392","journal-title":"Discret Appl Math"},{"key":"2437_CR8","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.dam.2023.06.013","volume":"339","author":"F Bonomo-Braberman","year":"2023","unstructured":"Bonomo-Braberman F, Brito GA (2023) Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs. Discret Appl Math 339:53\u201377","journal-title":"Discret Appl Math"},{"issue":"3","key":"2437_CR9","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth KS, Lueker GS (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13(3):335\u2013379","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"2437_CR10","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1137\/19M1299001","volume":"35","author":"S Chaplick","year":"2021","unstructured":"Chaplick S, Fomin FV, Golovach PA, Knop D, Zeman P (2021a) Kernelization of graph hamiltonicity: proper $$H$$-graphs. SIAM J Discret Math 35(2):840\u2013892","journal-title":"SIAM J Discret Math"},{"issue":"11","key":"2437_CR11","doi-asserted-by":"publisher","first-page":"3281","DOI":"10.1007\/s00453-021-00846-3","volume":"83","author":"S Chaplick","year":"2021","unstructured":"Chaplick S, T\u00f6pfer M, Voborn\u00edk J, Zeman P (2021b) On $$H$$-topological intersection graphs. Algorithmica 83(11):3281\u20133318","journal-title":"Algorithmica"},{"key":"2437_CR12","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1007\/s00453-022-01079-8","volume":"85","author":"N Chiarelli","year":"2023","unstructured":"Chiarelli N, Krnc M, Milani\u010d M, Pferschy U, Piva\u010d N, Schauer J (2023) Fair allocation of indivisible items with conflict graphs. Algorithmica 85:1459\u20131489","journal-title":"Algorithmica"},{"issue":"4","key":"2437_CR13","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil DG, Rotics U (2005) On the relationship between clique-width and treewidth. SIAM J Comput 34(4):825\u2013847","journal-title":"SIAM J Comput"},{"issue":"1\u20133","key":"2437_CR14","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle B, Olariu S (2000) Upper bounds to the clique width of graphs. Discret Appl Math 101(1\u20133):77\u2013114","journal-title":"Discret Appl Math"},{"key":"2437_CR15","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.tcs.2015.12.026","volume":"619","author":"B Courcelle","year":"2016","unstructured":"Courcelle B, Durand I (2016) Computations by fly-automata beyond monadic second-order logic. Theor Comput Sci 619:32\u201367","journal-title":"Theor Comput Sci"},{"issue":"2","key":"2437_CR16","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle B, Engelfriet J, Rozenberg G (1993) Handle-rewriting hypergraph grammars. J Comput Syst Sci 46(2):218\u2013270","journal-title":"J Comput Syst Sci"},{"issue":"2","key":"2437_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle B, Makowsky JA, Rotics U (2000) Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput Syst 33(2):125\u2013150","journal-title":"Theory Comput Syst"},{"key":"2437_CR18","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 FV, Kowalik \u0141, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Berlin"},{"key":"2437_CR19","unstructured":"Dallard C, Milani\u010d M, \u0160torgel K (2022a) Treewidth versus clique number. II. Tree-independence number. arXiv:2111.04543"},{"key":"2437_CR20","unstructured":"Dallard C, Milani\u010d M, \u0160torgel K (2022b) Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure. arXiv:2206.15092"},{"key":"2437_CR21","unstructured":"Dallard C, Fomin FV, Golovach P, Korhonen T, Milani\u010d M (2022c) Computing tree decompositions with small independence number. arXiv:2206.15092"},{"key":"2437_CR22","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.1016\/j.dam.2010.12.016","volume":"159","author":"A Darmann","year":"2011","unstructured":"Darmann A, Pferschy U, Schauer J, Woeginger GJ (2011) Paths, trees and matchings under disjunctive constraints. Discret Appl Math 159:1726\u20131735","journal-title":"Discret Appl Math"},{"issue":"6","key":"2437_CR23","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1137\/20M1320870","volume":"49","author":"M de Berg","year":"2020","unstructured":"de Berg M, Bodlaender HL, Kisfaludi-Bak S, Marx D, van der Zanden TC (2020) A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J Comput 49(6):1291\u20131331","journal-title":"SIAM J Comput"},{"key":"2437_CR24","series-title":"Banach Center Publ.","first-page":"233","volume-title":"Combinatorics and graph theory","author":"D de Werra","year":"1989","unstructured":"de Werra D (1989) Packing independent sets and transversals. Combinatorics and graph theory, vol 25. Banach Center Publ. PWN, Warsaw, pp 233\u2013240"},{"key":"2437_CR25","doi-asserted-by":"crossref","unstructured":"D\u00edaz J, Diner \u00d6Y, Serna M, Serra O (2021) On list $$k$$-coloring convex bipartite graphs. In: Gentile C, Stecca G, Ventura P (eds) Graphs and combinatorial optimization: from theory to applications: CTW2020 proceedings. Springer, pp 15\u201326","DOI":"10.1007\/978-3-030-63072-0_2"},{"issue":"4","key":"2437_CR26","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1016\/j.ejc.2011.12.005","volume":"33","author":"Z Dvo\u0159\u00e1k","year":"2012","unstructured":"Dvo\u0159\u00e1k Z, Kr\u00e1l\u2019 D (2012) Classes of graphs with small rank decompositions are $$\\chi $$-bounded. Eur J Comb 33(4):679\u2013683","journal-title":"Eur J Comb"},{"key":"2437_CR27","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/3-540-45477-2_12","volume-title":"Graph-theoretic concepts in computer science","author":"W Espelage","year":"2001","unstructured":"Espelage W, Gurski F, Wanke E (2001) How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. Graph-theoretic concepts in computer science, vol 2204. Lecture notes in computer science. Springer, Berlin, pp 117\u2013128"},{"issue":"2","key":"2437_CR28","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even G, Halld\u00f3rsson MM, Kaplan L, Ron D (2009) Scheduling with conflicts: online and offline algorithms. J Sched 12(2):199\u2013224","journal-title":"J Sched"},{"issue":"2","key":"2437_CR29","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"MR Fellows","year":"2009","unstructured":"Fellows MR, Rosamond FA, Rotics U, Szeider S (2009) Clique-width is NP-complete. SIAM J Discret Math 23(2):909\u2013939","journal-title":"SIAM J Discret Math"},{"issue":"7","key":"2437_CR30","doi-asserted-by":"publisher","first-page":"2170","DOI":"10.1007\/s00453-021-00822-x","volume":"83","author":"FV Fomin","year":"2021","unstructured":"Fomin FV, Golovach PA (2021) Subexponential parameterized algorithms and kernelization on almost chordal graphs. Algorithmica 83(7):2170\u20132214","journal-title":"Algorithmica"},{"key":"2437_CR31","doi-asserted-by":"crossref","unstructured":"Fomin FV, Korhonen T (2022) Fast FPT-approximation of branchwidth. In: STOC\u201922\u2014proceedings of the 54th annual ACM SIGACT symposium on theory of computing. ACM, New York, pp 886\u2013899","DOI":"10.1145\/3519935.3519996"},{"issue":"9","key":"2437_CR32","doi-asserted-by":"publisher","first-page":"2432","DOI":"10.1007\/s00453-020-00692-9","volume":"82","author":"FV Fomin","year":"2020","unstructured":"Fomin FV, Golovach PA, Raymond J-F (2020) On the tractability of optimization problems on $$H$$-graphs. Algorithmica 82(9):2432\u20132473","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"2437_CR33","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0304-3975(02)00725-9","volume":"299","author":"MU Gerber","year":"2003","unstructured":"Gerber MU, Kobler D (2003) Algorithms for vertex-partitioning problems on graphs with fixed clique-width. Theor Comput Sci 299(1\u20133):719\u2013734","journal-title":"Theor Comput Sci"},{"key":"2437_CR34","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization, vol 2. Algorithms and combinatorics: study and research texts. Springer, Berlin","DOI":"10.1007\/978-3-642-97881-4"},{"key":"2437_CR35","unstructured":"Gurski F (2008) A comparison of two approaches for polynomial time algorithms computing basic graph parameters. arXiv:0806.4073"},{"issue":"8","key":"2437_CR36","doi-asserted-by":"publisher","first-page":"2335","DOI":"10.1007\/s00453-022-00971-7","volume":"84","author":"A Jacob","year":"2022","unstructured":"Jacob A, Panolan F, Raman V, Sahlot V (2022) Structural parameterizations with modulator oblivion. Algorithmica 84(8):2335\u20132357","journal-title":"Algorithmica"},{"key":"2437_CR37","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.dam.2019.06.026","volume":"278","author":"L Jaffke","year":"2020","unstructured":"Jaffke L, Kwon O-J, Telle JA (2020) MIM-width I. Induced path problems. Discret Appl Math 278:153\u2013168","journal-title":"Discret Appl Math"},{"issue":"4","key":"2437_CR38","doi-asserted-by":"publisher","first-page":"2544","DOI":"10.1137\/19M1285895","volume":"35","author":"J Jeong","year":"2021","unstructured":"Jeong J, Kim EJ, Oum S-I (2021) Finding branch-decompositions of matroids, hypergraphs, and more. SIAM J Discret Math 35(4):2544\u20132617","journal-title":"SIAM J Discret Math"},{"issue":"4","key":"2437_CR39","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF00264533","volume":"15","author":"W Lipski","year":"1981","unstructured":"Lipski W, Preparata FP (1981) Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Inform 15(4):329\u2013346","journal-title":"Acta Inform"},{"issue":"1","key":"2437_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.orl.2006.01.009","volume":"35","author":"C Mannino","year":"2007","unstructured":"Mannino C, Oriolo G, Ricci F, Chandran S (2007) The stable set problem and the thinness of a graph. Oper Res Lett 35(1):1\u20139","journal-title":"Oper Res Lett"},{"key":"2437_CR41","unstructured":"Milani\u010d M, Rza\u0327\u017cewski P (2022) Tree decompositions with bounded independence number: beyond independent sets. arXiv:2209.12315"},{"issue":"3","key":"2437_CR42","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1287\/ijoc.1090.0355","volume":"22","author":"A Muritiba","year":"2010","unstructured":"Muritiba A, Iori M, Malaguti E, Toth P (2010) Algorithms for the bin packing problem with conflicts. INFORMS J Comput 22(3):401\u2013415","journal-title":"INFORMS J Comput"},{"key":"2437_CR43","doi-asserted-by":"crossref","unstructured":"Oum Si (2009) Approximating rank-width and clique-width quickly. ACM Trans Algorithms 5(1): Art. 10, 20","DOI":"10.1145\/1435375.1435385"},{"issue":"4","key":"2437_CR44","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S-I Oum","year":"2006","unstructured":"Oum S-I, Seymour P (2006) Approximating clique-width and branch-width. J Comb Theory Ser B 96(4):514\u2013528","journal-title":"J Comb Theory Ser B"},{"issue":"2","key":"2437_CR45","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy U, Schauer J (2009) The knapsack problem with conflict graphs. J Graph Algorithms Appl 13(2):233\u2013249","journal-title":"J Graph Algorithms Appl"},{"issue":"4","key":"2437_CR46","doi-asserted-by":"publisher","first-page":"1300","DOI":"10.1007\/s10878-016-0035-7","volume":"33","author":"U Pferschy","year":"2017","unstructured":"Pferschy U, Schauer J (2017) Approximation of knapsack problems with conflict and forcing graphs. J Comb Optim 33(4):1300\u20131323","journal-title":"J Comb Optim"},{"issue":"3","key":"2437_CR47","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1002\/jgt.22792","volume":"100","author":"A Rafiey","year":"2022","unstructured":"Rafiey A (2022) Recognizing interval bigraphs by forbidden patterns. J Graph Theory 100(3):504\u2013529","journal-title":"J Graph Theory"},{"issue":"1\u20133","key":"2437_CR48","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.tcs.2007.03.043","volume":"377","author":"M Rao","year":"2007","unstructured":"Rao M (2007) MSOL partitioning problems on graphs of bounded treewidth and clique-width. Theor Comput Sci 377(1\u20133):260\u2013267","journal-title":"Theor Comput Sci"},{"key":"2437_CR49","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.eswa.2019.01.052","volume":"124","author":"LFM Santos","year":"2019","unstructured":"Santos LFM, Iwayama RS, Cavalcanti LB, Turi LM, de Souza Morais FE, Mormilho G, Cunha CB (2019) A variable neighborhood search algorithm for the bin packing problem with compatible categories. Expert Syst Appl 124:209\u2013225","journal-title":"Expert Syst Appl"},{"issue":"3","key":"2437_CR50","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/jgt.22601","volume":"95","author":"A Scott","year":"2020","unstructured":"Scott A, Seymour P (2020) A survey of $$\\chi $$-boundedness. J Graph Theory 95(3):473\u2013504","journal-title":"J Graph Theory"},{"key":"2437_CR51","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/3-540-46784-X_16","volume-title":"Graph-theoretic concepts in computer science","author":"K Skodinis","year":"1999","unstructured":"Skodinis K (1999) Efficient analysis of graphs with small minimal separators. Graph-theoretic concepts in computer science, vol 1665. Lecture notes in computer science. Springer, Berlin, pp 155\u2013166"},{"key":"2437_CR52","series-title":"Fields institute monographs","volume-title":"Efficient graph representations","author":"JP Spinrad","year":"2003","unstructured":"Spinrad JP (2003) Efficient graph representations, vol 19. Fields institute monographs. American Mathematical Society, Providence"},{"key":"2437_CR53","doi-asserted-by":"crossref","unstructured":"Yolov N (2018) Minor-matching hypertree width. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, SIAM, Philadelphia, PA, pp 219\u2013233","DOI":"10.1137\/1.9781611975031.16"}],"container-title":["Computational and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-023-02437-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s40314-023-02437-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s40314-023-02437-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,6]],"date-time":"2023-10-06T03:45:47Z","timestamp":1696563947000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s40314-023-02437-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,11]]},"references-count":53,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["2437"],"URL":"https:\/\/doi.org\/10.1007\/s40314-023-02437-0","relation":{},"ISSN":["2238-3603","1807-0302"],"issn-type":[{"type":"print","value":"2238-3603"},{"type":"electronic","value":"1807-0302"}],"subject":[],"published":{"date-parts":[[2023,9,11]]},"assertion":[{"value":"1 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 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 conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"302"}}