{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T22:14:18Z","timestamp":1778883258572,"version":"3.51.4"},"reference-count":66,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T00:00:00Z","timestamp":1670803200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T00:00:00Z","timestamp":1670803200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005203","name":"OeAD-GmbH","doi-asserted-by":"publisher","award":["SI 22\/2018"],"award-info":[{"award-number":["SI 22\/2018"]}],"id":[{"id":"10.13039\/501100005203","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005203","name":"OeAD-GmbH","doi-asserted-by":"publisher","award":["SI 31\/2020"],"award-info":[{"award-number":["SI 31\/2020"]}],"id":[{"id":"10.13039\/501100005203","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["BI-AT\/18-19-005"],"award-info":[{"award-number":["BI-AT\/18-19-005"]}],"id":[{"id":"10.13039\/501100004329","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"],"award-info":[{"award-number":["BI-AT\/20-21-015"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["I0-0035"],"award-info":[{"award-number":["I0-0035"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["P1-0404, P1-0285, P1-0383, N1-0102, N1-0160, N1-0210, J1-3001, J1-3002, J1-3003, J1-4008, J5-4596"],"award-info":[{"award-number":["P1-0404, P1-0285, P1-0383, 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\/100010684","name":"H2020 Spreading Excellence and Widening Participation","doi-asserted-by":"publisher","award":["739574"],"award-info":[{"award-number":["739574"]}],"id":[{"id":"10.13039\/100010684","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009057","name":"University of Graz","doi-asserted-by":"crossref","award":["Colibri"],"award-info":[{"award-number":["Colibri"]}],"id":[{"id":"10.13039\/501100009057","id-type":"DOI","asserted-by":"crossref"}]},{"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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the fair allocation of indivisible items to several agents and add a graph theoretical perspective to this classical problem. Namely, we introduce an incompatibility relation between pairs of items described in terms of a conflict graph. Every subset of items assigned to one agent has to form an independent set in this graph. Thus, the allocation of items to the agents corresponds to a partial coloring of the conflict graph. Every agent has its own profit valuation for every item. Aiming at a fair allocation, our goal is the maximization of the lowest total profit of items allocated to any one of the agents. The resulting optimization problem contains, as special cases, both <jats:sc>Partition<\/jats:sc> and <jats:sc>Independent Set<\/jats:sc>. In our contribution we derive complexity and algorithmic results depending on the properties of the given graph. We show that the problem is strongly NP-hard for bipartite graphs and their line graphs, and solvable in pseudo-polynomial time for the classes of chordal graphs, cocomparability graphs, biconvex bipartite graphs, and graphs of bounded treewidth. Each of the pseudo-polynomial algorithms can also be turned into a fully polynomial approximation scheme (FPTAS).<\/jats:p>","DOI":"10.1007\/s00453-022-01079-8","type":"journal-article","created":{"date-parts":[[2022,12,12]],"date-time":"2022-12-12T06:02:52Z","timestamp":1670824972000},"page":"1459-1489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Fair Allocation of Indivisible Items with Conflict Graphs"],"prefix":"10.1007","volume":"85","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"}]},{"given":"Nevena","family":"Piva\u010d","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":[[2022,12,12]]},"reference":[{"issue":"1\u20133","key":"1079_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0166-218X(99)00217-6","volume":"103","author":"N Abbas","year":"2000","unstructured":"Abbas, N., Stewart, L.K.: Biconvex graphs: ordering and algorithms. Discrete Appl. Math. 103(1\u20133), 1\u201319 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"7","key":"1079_CR2","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1016\/j.dam.2008.08.020","volume":"158","author":"L Addario-Berry","year":"2010","unstructured":"Addario-Berry, L., Kennedy, W.S., King, A.D., Li, Z., Reed, B.: Finding a maximum-weight induced $$k$$-partite subgraph of an $$i$$-triangulated graph. Discrete Appl. Math. 158(7), 765\u2013770 (2010)","journal-title":"Discrete Appl. Math."},{"key":"1079_CR3","unstructured":"Alekseev, V.E.: The effect of local constraints on the complexity of determination of the graph independence number. In: Combinatorial-Algebraic Methods in Applied Mathematics, pp. 3\u201313. Gorky University Press (1982) (in Russian)"},{"issue":"4","key":"1079_CR4","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1145\/3147173","volume":"13","author":"G Amanatidis","year":"2017","unstructured":"Amanatidis, G., Markakis, E., Nikzad, A., Saberi, A.: Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms 13(4), 52 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"1079_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3070694","volume":"13","author":"C Annamalai","year":"2017","unstructured":"Annamalai, C., Kalaitzis, C., Svensson, O.: Combinatorial algorithm for restricted max\u2013min fair allocation. ACM Trans. Algorithms 13(3), 1\u201328 (2017)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"1079_CR6","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"issue":"7","key":"1079_CR7","doi-asserted-by":"crossref","first-page":"2970","DOI":"10.1137\/080723491","volume":"39","author":"A Asadpour","year":"2010","unstructured":"Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput. 39(7), 2970\u20132989 (2010)","journal-title":"SIAM J. Comput."},{"key":"1079_CR8","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1002\/(SICI)1099-1425(199808)1:2<67::AID-JOS6>3.0.CO;2-Y","volume":"1","author":"Y Azar","year":"1998","unstructured":"Azar, Y., Epstein, L.: On-line machine covering. J. Sched. 1, 67\u201377 (1998)","journal-title":"J. Sched."},{"key":"1079_CR9","doi-asserted-by":"crossref","unstructured":"Bansal, N., Sviridenko, M.: The Santa Claus problem. In: STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 31\u201340 (2006)","DOI":"10.1145\/1132516.1132522"},{"issue":"1","key":"1079_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3381525","volume":"8","author":"S Barman","year":"2020","unstructured":"Barman, S., Krishnamurthy, S.K.: Approximation algorithms for maximin fair division. ACM Trans. Econ. Comput. 8(1), 1\u201328 (2020)","journal-title":"ACM Trans. Econ. Comput."},{"key":"1079_CR11","first-page":"1","volume":"65","author":"X Bei","year":"2021","unstructured":"Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. Theory Comput. Syst. 65, 1\u201325 (2021)","journal-title":"Theory Comput. Syst."},{"issue":"1\u20132","key":"1079_CR12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0012-365X(89)90193-3","volume":"74","author":"C Berge","year":"1989","unstructured":"Berge, C.: Minimax relations for the partial $$q$$-colorings of a graph. Discrete Math. 74(1\u20132), 3\u201314 (1989)","journal-title":"Discrete Math."},{"issue":"3","key":"1079_CR13","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1120680.1120683","volume":"5","author":"I Bezakova","year":"2005","unstructured":"Bezakova, I., Dani, V.: Allocating indivisible goods. ACM SIGecom Exchanges 5(3), 11\u201318 (2005)","journal-title":"ACM SIGecom Exchanges"},{"key":"1079_CR14","doi-asserted-by":"crossref","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computation, volume\u00a056 of IMA Vol. Math. Appl., pp. 1\u201329. Springer, New York (1993)","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"1079_CR15","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Jansen, K.: 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, pp. 291\u2013300. Springer (1993)","DOI":"10.1007\/3-540-57182-5_21"},{"issue":"6","key":"1079_CR16","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"1079_CR17","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Cechl\u00e1rov\u00e1, K., Elkind, E., Igarashi, A., Peters, D.: Fair division of a graph. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 135\u2013141 (2017)","DOI":"10.24963\/ijcai.2017\/20"},{"key":"1079_CR18","doi-asserted-by":"crossref","unstructured":"Bouveret, S., Chevaleyre, Y., Maudet, N.: Fair allocation of indivisible goods. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice, pp. 284\u2013310. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781107446984.013"},{"key":"1079_CR19","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. Society for Industrial and Applied Mathematics (SIAM), SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"1079_CR20","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2020.105176","volume":"128","author":"SS Brito","year":"2021","unstructured":"Brito, S.S., Santos, H.G.: Preprocessing and cutting planes with conflict graphs. Comput. Oper. Res. 128, 105176 (2021)","journal-title":"Comput. Oper. Res."},{"key":"1079_CR21","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proceedings Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 107\u2013116 (2009)","DOI":"10.1109\/FOCS.2009.51"},{"key":"1079_CR22","doi-asserted-by":"crossref","unstructured":"Chiarelli, N., Krnc, M., Milani\u010d, M., Pferschy, U., Piva\u010d, N., Schauer, J.: Fair packing of independent sets. In: Combinatorial Algorithms\u201431st International Workshop, IWOCA 2020, volume 12126 of LNCS. Springer, pp. 154\u2013165 (2020)","DOI":"10.1007\/978-3-030-48966-3_12"},{"issue":"2","key":"1079_CR23","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1016\/j.ejor.2020.07.023","volume":"289","author":"S Coniglio","year":"2021","unstructured":"Coniglio, S., Furini, F., San Segundo, P.: A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts. Eur. J. Oper. Res. 289(2), 435\u2013455 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"1079_CR24","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"issue":"1","key":"1079_CR25","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs: I: recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"1079_CR26","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"10","key":"1079_CR27","doi-asserted-by":"crossref","first-page":"2841","DOI":"10.1007\/s00453-020-00706-6","volume":"82","author":"KK Dabrowski","year":"2020","unstructured":"Dabrowski, K.K., Feghali, C., Johnson, M., Paesani, G., Paulusma, D., Rz\u0105\u017cewski, P.: On cycle transversals and their connected variants in the absence of a small linear forest. Algorithmica 82(10), 2841\u20132866 (2020)","journal-title":"Algorithmica"},{"key":"1079_CR28","doi-asserted-by":"crossref","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, G.: Paths, trees and matchings under disjunctive constraints. Discrete Appl. Math. 159, 1726\u20131735 (2011)","journal-title":"Discrete Appl. Math."},{"key":"1079_CR29","doi-asserted-by":"crossref","unstructured":"de\u00a0Werra, D.: Packing independent sets and transversals. In: Combinatorics and Graph Theory, volume\u00a025 of Banach Center Publ., pp. 233\u2013240. PWN, Warsaw (1989)","DOI":"10.4064\/-25-1-233-240"},{"issue":"2","key":"1079_CR30","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1137\/0603019","volume":"3","author":"BL Deuermeyer","year":"1982","unstructured":"Deuermeyer, B.L., Friesen, D.K., Langston, M.A.: Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM J. Algebraic Discrete Methods 3(2), 190\u2013196 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"1079_CR31","doi-asserted-by":"crossref","first-page":"1603","DOI":"10.1287\/mnsc.48.12.1603.445","volume":"48","author":"T Erlebach","year":"2002","unstructured":"Erlebach, T., Kellerer, H., Pferschy, U.: Multiobjective knapsack problems. Manag. Sci. 48, 1603\u20131612 (2002)","journal-title":"Manag. Sci."},{"issue":"2","key":"1079_CR32","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10951-008-0089-1","volume":"12","author":"G Even","year":"2009","unstructured":"Even, G., Halld\u00f3rsson, M.M., Kaplan, L., Ron, D.: Scheduling with conflicts: online and offline algorithms. J. Sched. 12(2), 199\u2013224 (2009)","journal-title":"J. Sched."},{"key":"1079_CR33","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2019.104805","volume":"113","author":"P Factorovich","year":"2020","unstructured":"Factorovich, P., M\u00e9ndez-D\u00edaz, I., Zabala, P.: Pickup and delivery problem with incompatibility constraints. Comput. Oper. Res. 113, 104805 (2020)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1079_CR34","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.ejor.2022.02.014","volume":"303","author":"K Fleszar","year":"2022","unstructured":"Fleszar, K.: A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation. Eur. J. Oper. Res. 303(1), 37\u201353 (2022)","journal-title":"Eur. J. Oper. Res."},{"key":"1079_CR35","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.dam.2016.01.036","volume":"234","author":"H Furma\u0144czyk","year":"2018","unstructured":"Furma\u0144czyk, H., Kubale, M.: Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines. Discrete Appl. Math. 234, 210\u2013217 (2018)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1079_CR36","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1002\/net.3230170407","volume":"17","author":"F Gavril","year":"1987","unstructured":"Gavril, F.: Algorithms for maximum $$k$$-colorings and $$k$$-coverings of transitive graphs. Networks 17(4), 465\u2013470 (1987)","journal-title":"Networks"},{"issue":"3","key":"1079_CR37","doi-asserted-by":"crossref","first-page":"1038","DOI":"10.1287\/moor.2020.1096","volume":"46","author":"M Ghodsi","year":"2021","unstructured":"Ghodsi, M., Hajiaghayi, M.T., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods: improvement. Math. Oper. Res. 46(3), 1038\u20131053 (2021)","journal-title":"Math. Oper. Res."},{"key":"1079_CR38","unstructured":"Golovin, D.: Max\u2013min fair allocation of indivisible goods. Technical Report CMU-CS-05-144, Carnegie Mellon University (2005)"},{"key":"1079_CR39","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, volume\u00a057 of Annals of Discrete Mathematics. Elsevier, second edition (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"1079_CR40","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics: Study and Research Texts, vol. 2. Springer-Verlag, Berlin (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"key":"1079_CR41","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.trc.2015.01.010","volume":"55","author":"Z-H Hu","year":"2015","unstructured":"Hu, Z.-H., Sheu, J.-B., Zhao, L., Lu, C.-C.: A dynamic closed-loop vehicle routing problem with uncertainty and incompatible goods. Transp. Res. Part C: Emerg. Technol. 55, 273\u2013297 (2015)","journal-title":"Transp. Res. Part C: Emerg. Technol."},{"key":"1079_CR42","unstructured":"Khodamoradi, K., Krishnamurti, R., Rafiey, A., Stamoulis, G.: PTAS for ordered instances of resource allocation problems. In: Proceedings of the 33rd International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, volume\u00a024 of LIPICS, pp. 461\u2013473 (2013)"},{"issue":"2","key":"1079_CR43","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1145\/3140756","volume":"65","author":"D Kurokawa","year":"2018","unstructured":"Kurokawa, D., Procaccia, A.D., Wang, J.: Fair enough: guaranteeing approximate maximin shares. J ACM 65(2), 675\u2013692 (2018)","journal-title":"J ACM"},{"issue":"1","key":"1079_CR44","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1287\/ijoc.2021.1086","volume":"34","author":"O Kuryatnikova","year":"2022","unstructured":"Kuryatnikova, O., Sotirov, R., Vera, J.C.: The maximum $$k$$-colorable subgraph problem and related problems. INFORMS J. Comput. 34(1), 656\u2013669 (2022)","journal-title":"INFORMS J. Comput."},{"key":"1079_CR45","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1145\/321850.321853","volume":"21","author":"PGH Lehot","year":"1974","unstructured":"Lehot, P.G.H.: An optimal algorithm to detect a line graph and output its root graph. J. Assoc. Comput. Mach. 21, 569\u2013575 (1974)","journal-title":"J. Assoc. Comput. Mach."},{"key":"1079_CR46","doi-asserted-by":"crossref","unstructured":"Mallek, A., Boudhar, M.: Scheduling on uniform machines with a conflict graph: complexity and resolution. Int. Trans. Oper. Res., to appear (2022)","DOI":"10.1111\/itor.13170"},{"key":"1079_CR47","doi-asserted-by":"crossref","unstructured":"Mastrolilli, M., Stamoulis, G.: Restricted max-min fair allocations with inclusion-free intervals. In: Proceedings of International Computing and Combinatorics Conference COCOON 2012, volume 7434 of LNCS, pp. 98\u2013108. Springer (2012)","DOI":"10.1007\/978-3-642-32241-9_9"},{"issue":"12","key":"1079_CR48","doi-asserted-by":"crossref","first-page":"2061","DOI":"10.14778\/3407790.3407809","volume":"13","author":"D Miao","year":"2020","unstructured":"Miao, D., Cai, Z., Li, J., Gao, X., Liu, X.: The computation of optimal subset repairs. Proc. VLDB Endowm. 13(12), 2061\u20132074 (2020)","journal-title":"Proc. VLDB Endowm."},{"issue":"1","key":"1079_CR49","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/s00453-018-0431-8","volume":"81","author":"N Misra","year":"2019","unstructured":"Misra, N., Panolan, F., Rai, A., Raman, V., Saurabh, S.: Parameterized algorithms for max colorable induced subgraph problem on perfect graphs. Algorithmica 81(1), 26\u201346 (2019)","journal-title":"Algorithmica"},{"issue":"3","key":"1079_CR50","doi-asserted-by":"crossref","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.: Algorithms for the bin packing problem with conflicts. INFORMS J. Comput. 22(3), 401\u2013415 (2010)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"1079_CR51","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1515\/ausi-2015-0004","volume":"6","author":"D P\u00e1lv\u00f6lgi","year":"2014","unstructured":"P\u00e1lv\u00f6lgi, D.: Partitioning to three matchings of given size is NP-complete for bipartite graphs. Acta Universitatis Sapientiae, Informatica 6(2), 206\u2013209 (2014)","journal-title":"Acta Universitatis Sapientiae, Informatica"},{"issue":"2","key":"1079_CR52","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233\u2013249 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"1079_CR53","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10878-011-9438-7","volume":"26","author":"U Pferschy","year":"2013","unstructured":"Pferschy, U., Schauer, J.: The maximum flow problem with disjunctive constraints. J. Comb. Optim. 26(1), 109\u2013119 (2013)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"1079_CR54","doi-asserted-by":"crossref","first-page":"1300","DOI":"10.1007\/s10878-016-0035-7","volume":"33","author":"U Pferschy","year":"2017","unstructured":"Pferschy, U., Schauer, J.: Approximation of knapsack problems with conflict and forcing graphs. J. Comb. Optim. 33(4), 1300\u20131323 (2017)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"1079_CR55","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett. 32(4), 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"1079_CR56","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"ND Roussopoulos","year":"1973","unstructured":"Roussopoulos, N.D.: A max $$\\{m, n\\}$$ algorithm for determining the graph $$H$$ from its line graph $$G$$. Inf. Process. Lett. 2, 108\u2013112 (1973)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1079_CR57","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/ijoc.1120.0499","volume":"25","author":"R Sadykov","year":"2013","unstructured":"Sadykov, R., Vanderbeck, F.: Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J. Comput. 25(2), 244\u2013255 (2013)","journal-title":"INFORMS J. Comput."},{"key":"1079_CR58","doi-asserted-by":"crossref","DOI":"10.1016\/j.cor.2022.105763","volume":"143","author":"S Saffari","year":"2022","unstructured":"Saffari, S., Fathi, Y.: Set covering problem with conflict constraints. Comput. Oper. Res. 143, 105763 (2022)","journal-title":"Comput. Oper. Res."},{"key":"1079_CR59","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.eswa.2019.01.052","volume":"124","author":"LFM Santos","year":"2019","unstructured":"Santos, L.F.M., Iwayama, R.S., Cavalcanti, L.B., Turi, L.M., de Souza Morais, F.E., Mormilho, G., Cunha, C.B.: A variable neighborhood search algorithm for the bin packing problem with compatible categories. Expert Syst. Appl. 124, 209\u2013225 (2019)","journal-title":"Expert Syst. Appl."},{"key":"1079_CR60","unstructured":"Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency., volume\u00a024 of Algorithms and Combinatorics. Springer (2003)"},{"issue":"3","key":"1079_CR61","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","volume":"14","author":"J Spinrad","year":"1985","unstructured":"Spinrad, J.: On comparability and permutation graphs. SIAM J. Comput. 14(3), 658\u2013670 (1985)","journal-title":"SIAM J. Comput."},{"key":"1079_CR62","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient graph representations. Fields Institute Monographs, vol. 19. American Mathematical Society, Providence, RI (2003)","DOI":"10.1090\/fim\/019"},{"key":"1079_CR63","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A Tucker","year":"1972","unstructured":"Tucker, A.: A structure theorem for the consecutive $$1$$\u2019s property. J. Comb. Theory Ser. B 12, 153\u2013162 (1972)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"1079_CR64","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0167-6377(96)00055-7","volume":"20","author":"GJ Woeginger","year":"1997","unstructured":"Woeginger, G.J.: A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. 20(4), 149\u2013154 (1997)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1079_CR65","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(87)90107-4","volume":"24","author":"M Yannakakis","year":"1987","unstructured":"Yannakakis, M., Gavril, F.: The maximum $$k$$-colorable subgraph problem for chordal graphs. Inf. Process. Lett. 24(2), 133\u2013137 (1987)","journal-title":"Inf. Process. Lett."},{"key":"1079_CR66","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01079-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01079-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01079-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,25]],"date-time":"2023-04-25T00:04:34Z","timestamp":1682381074000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01079-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,12]]},"references-count":66,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1079"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01079-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,12]]},"assertion":[{"value":"8 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest related to this work.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}