{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:50:22Z","timestamp":1780822222062,"version":"3.54.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,6,6]],"date-time":"2016-06-06T00:00:00Z","timestamp":1465171200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"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":["J Comb Optim"],"published-print":{"date-parts":[[2017,5]]},"DOI":"10.1007\/s10878-016-0035-7","type":"journal-article","created":{"date-parts":[[2016,6,6]],"date-time":"2016-06-06T10:33:40Z","timestamp":1465209220000},"page":"1300-1323","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":43,"title":["Approximation of knapsack problems with conflict and forcing graphs"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8881-1497","authenticated-orcid":false,"given":"Ulrich","family":"Pferschy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2268-0612","authenticated-orcid":false,"given":"Joachim","family":"Schauer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,6,6]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Berry A, Bordat J-P, Cogis O (1999) Generating all the minimal separators of a graph. In: Graph-theoretic concepts in computer science. Lecture notes in computer science, vol 1665. Springer, Heidelberg, pp 167\u2013172","DOI":"10.1007\/3-540-46784-X_17"},{"key":"35_CR2","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.dam.2014.11.018","volume":"184","author":"A Berry","year":"2015","unstructured":"Berry A, Brandst\u00e4dt A, Giakoumakis V, Maffray F (2015) Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds. Discret Appl Math 184:50\u201361","journal-title":"Discret Appl Math"},{"issue":"3","key":"35_CR3","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender HL, Koster AMCA (2008) Combinatorial optimization on graphs of bounded treewidth. Comput J 51(3):255\u2013269","journal-title":"Comput J"},{"issue":"1","key":"35_CR4","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9 V, Todinca I (2001) Treewidth and minimum fill-in: grouping the minimal separators. SIAM J Comput 31(1):212\u2013232","journal-title":"SIAM J Comput"},{"issue":"1\u2014-2","key":"35_CR5","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9 V, Todinca I (2002) Listing all potential maximal cliques of a graph. Theor Comput Sci 276(1\u2014-2):17\u201332","journal-title":"Theor Comput Sci"},{"issue":"3","key":"35_CR6","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.ipl.2011.09.015","volume":"112","author":"A Brandst\u00e4dt","year":"2012","unstructured":"Brandst\u00e4dt A, Giakoumakis V (2012) Maximum weight independent sets in hole-and co-chair-free graphs. Inf Process Lett 112(3):67\u201371","journal-title":"Inf Process Lett"},{"issue":"2","key":"35_CR7","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/j.ipl.2014.09.019","volume":"115","author":"A Brandst\u00e4dt","year":"2015","unstructured":"Brandst\u00e4dt A, Giakoumakis V (2015) Addendum to: maximum weight independent sets in hole- and co-chair-free graphs. Inf Process Lett 115(2):345\u2013350","journal-title":"Inf Process Lett"},{"issue":"1","key":"35_CR8","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/j.tcs.2007.09.031","volume":"389","author":"A Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt A, Ho\u00e0ng CT (2007) On clique separators, nearly chordal graphs, and the maximum weight stable set problem. Theor Comput Sci 389(1):295\u2013306","journal-title":"Theor Comput Sci"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt A, Le VB, Spinrad JP (1999) SIAM monographs on discrete mathematics and applications. Graph classes: a survey. Philadelphia","DOI":"10.1137\/1.9780898719796"},{"key":"35_CR10","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1137\/090750822","volume":"24","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt A, Lozin VV, Mosca R (2010) Independent sets of maximum weight in apple-free graphs. SIAM J Discret Math 24:239\u2013254","journal-title":"SIAM J Discret Math"},{"key":"35_CR11","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/j.dam.2011.10.031","volume":"160","author":"A Brandst\u00e4dt","year":"2012","unstructured":"Brandst\u00e4dt A, Giakoumakis V, Maffray F (2012) Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences. Discret Appl Math 160:471\u2013478","journal-title":"Discret Appl Math"},{"issue":"1\u20133","key":"35_CR12","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0012-365X(02)00803-8","volume":"266","author":"K Cameron","year":"2003","unstructured":"Cameron K, Sritharan R, Tang Y (2003) Finding a maximum induced matching in weakly chordal graphs. Discret Math 266(1\u20133):133\u2013142","journal-title":"Discret Math"},{"key":"35_CR13","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 GJ (2011) Paths, trees and matchings under disjunctive constraints. Discret Appl Math 159:1726\u20131735","journal-title":"Discret Appl Math"},{"key":"35_CR14","doi-asserted-by":"crossref","unstructured":"Demaine ED, Hajiaghayi MT, Kawarabayashi K (2005) Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637\u2013646","DOI":"10.1109\/SFCS.2005.14"},{"key":"35_CR15","volume-title":"Graph theory","author":"R Diestel","year":"2012","unstructured":"Diestel R (2012) Graph theory, 4th edn. Springer, Heidelberg","edition":"4"},{"issue":"2","key":"35_CR16","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, Kaplan L, Ron D (2009) Scheduling with conflicts: online and offline algorithms. J Sched 12(2):199\u2013224","journal-title":"J Sched"},{"key":"35_CR17","unstructured":"Fomin FV, Villanger Y (2010) Finding induced subgraphs via minimal triangulations. In: Proceedings of the 27th international symposium on theoretical aspects of computer science, STACS. Leibniz international proceedings in informatics, vol 5, pp 383\u2013394"},{"issue":"1","key":"35_CR18","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai T (1967) Transitiv orientierbare graphen. Acta Math Hung 18(1):25\u201366","journal-title":"Acta Math Hung"},{"issue":"1","key":"35_CR19","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J (1999) Clique is hard to approximate within $$n^{1-\\varepsilon }$$ n 1 - \u03b5 . Acta Math 182(1):105\u2013142","journal-title":"Acta Math"},{"issue":"1","key":"35_CR20","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BF01788689","volume":"5","author":"R Hayward","year":"1989","unstructured":"Hayward R, Ho\u00e0ng CT, Maffray F (1989) Optimizing weakly triangulated graphs. Gr Comb 5(1):339\u2013349","journal-title":"Gr Comb"},{"issue":"2","key":"35_CR21","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/1240233.1240237","volume":"3","author":"RB Hayward","year":"2007","unstructured":"Hayward RB, Spinrad JP, Sritharan R (2007) Improved algorithms for weakly chordal graphs. ACM Trans Algorithms 3(2):14","journal-title":"ACM Trans Algorithms"},{"issue":"1","key":"35_CR22","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1504\/IJOR.2012.044026","volume":"13","author":"M Hifi","year":"2012","unstructured":"Hifi M, Otmani N (2012) An algorithm for the disjunctively constrained knapsack problem. Int J Oper Res 13(1):22\u201343","journal-title":"Int J Oper Res"},{"key":"35_CR23","doi-asserted-by":"crossref","unstructured":"Hifi M, Saleh S, Wu L (2014) A fast large neighborhood search for disjunctively constrained knapsack problems. In: Proceedings of 3rd international symposium on combinatorial optimization, ISCO 2014. Lecture notes in computer science, vol 8596. Springer, Heidelberg, pp 396\u2013407","DOI":"10.1007\/978-3-319-09174-7_34"},{"key":"35_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Heidelberg"},{"key":"35_CR25","unstructured":"Lokshtanov D, Vatshelle M, Villanger Y (2014) Independent set in $$\\text{P}_5$$ P 5 -free graphs in polynomial time. In: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570\u2013581"},{"key":"35_CR26","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.jda.2008.04.001","volume":"6","author":"VV Lozin","year":"2008","unstructured":"Lozin VV, Milani\u010d M (2008) A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. J Discret Algorithms 6:595\u2013604","journal-title":"J Discret Algorithms"},{"key":"35_CR27","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell RM, Spinrad JP (1999) Modular decomposition and transitive orientation. Discret Math 201:189\u2013241","journal-title":"Discret Math"},{"key":"35_CR28","doi-asserted-by":"crossref","unstructured":"Milani\u010d M, Monnot J (2008) The complexity of the exact weighted independent set problem. In: Combinatorial optimization\u2014theoretical computer science: interfaces and perspectives, Wiley-ISTE, New York, pp 393\u2013432","DOI":"10.1002\/9780470611098.ch16"},{"key":"35_CR29","doi-asserted-by":"crossref","unstructured":"M\u00f6hring RH, Rademacher FJ (1984) Substitution decomposition for discrete structures and connections with combinatorial optimization. In: Proceedings of the workshop on algebraic structures in operations research. North-Holland mathematics studies, Published also as annals of discrete mathematics 19, vol 95. Elsevier, Amsterdam, pp 257\u2013355","DOI":"10.1016\/S0304-0208(08)72966-9"},{"key":"35_CR30","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 (2010) Algorithms for the bin packing problem with conflicts. INFORMS J Comput 22:401\u2013415","journal-title":"INFORMS J Comput"},{"issue":"4","key":"35_CR31","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1016\/j.cor.2012.10.022","volume":"40","author":"T \u00d6ncan","year":"2013","unstructured":"\u00d6ncan T, Zhang R, Punnen AP (2013) The minimum cost perfect matching problem with conflict pair constraints. Comput Oper Res 40(4):920\u2013930","journal-title":"Comput Oper Res"},{"issue":"2","key":"35_CR32","doi-asserted-by":"crossref","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 Gr Algorithms Appl 13(2):233\u2013249","journal-title":"J Gr Algorithms Appl"},{"issue":"1","key":"35_CR33","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 (2013) The maximum flow problem with disjunctive constraints. J Comb Optim 26(1):109\u2013119","journal-title":"J Comb Optim"},{"issue":"2","key":"35_CR34","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/j.tcs.2007.03.006","volume":"382","author":"K Pruhs","year":"2007","unstructured":"Pruhs K, Woeginger GJ (2007) Approximation schemes for a class of subset selection problems. Theor Comput Sci 382(2):151\u2013156","journal-title":"Theor Comput Sci"},{"issue":"2","key":"35_CR35","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 (2013) Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J Comput 25(2):244\u2013255","journal-title":"INFORMS J Comput"},{"issue":"2","key":"35_CR36","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0166-218X(93)E0161-Q","volume":"59","author":"J Spinrad","year":"1995","unstructured":"Spinrad J, Sritharan R (1995) Algorithms for weakly triangulated graphs. Discret Appl Math 59(2):181\u2013191","journal-title":"Discret Appl Math"},{"issue":"2","key":"35_CR37","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"RE Tarjan","year":"1985","unstructured":"Tarjan RE (1985) Decomposition by clique separators. Discret Math 55(2):221\u2013232","journal-title":"Discret Math"},{"key":"35_CR38","first-page":"281","volume":"21","author":"SH Whitesides","year":"1984","unstructured":"Whitesides SH (1984) A method for solving certain graph recognition and optimization problems, with applications to perfect graphs. Ann Discret Math 21:281\u2013297 Published also as North-Holland Mathematics Studies 88","journal-title":"Ann Discret Math"},{"key":"35_CR39","first-page":"2864","volume":"43","author":"T Yamada","year":"2002","unstructured":"Yamada T, Kataoka S, Watanabe K (2002) Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Inf Process Soc Jpn J 43:2864\u20132870","journal-title":"Inf Process Soc Jpn J"},{"issue":"2","key":"35_CR40","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.disopt.2010.08.001","volume":"8","author":"R Zhang","year":"2011","unstructured":"Zhang R, Kabadi SN, Punnen AP (2011) The minimum spanning tree problem with conflict constraints and its variations. Discret Optim 8(2):191\u2013205","journal-title":"Discret Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0035-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-016-0035-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0035-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0035-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T11:08:52Z","timestamp":1718622532000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-016-0035-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,6]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,5]]}},"alternative-id":["35"],"URL":"https:\/\/doi.org\/10.1007\/s10878-016-0035-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,6]]}}}