Vi utökar det klassiska 0-1 knapsack problemet genom att införa disjunktiva begränsningar för par av objekt som inte får packas ihop i knapsacken. Dessa begränsningar representeras av kanterna på ett konfliktdiagram vars hörn motsvarar objekten i Knapsack-problemet. Liknande tillstånd behandlades i litteraturen för förpackning och schemaläggning problem. För Knapsack problem med konfliktgrafer, exakta och heuristiska algoritmer föreslogs i det förflutna. Medan problemet är starkt NP-hård i allmänhet, presenterar vi pseudopolynomalgoritmer för två speciella grafklasser, nämligen grafer av avgränsad trädbredd (inklusive träd och serieparallell grafer) och ackord diagram. Från dessa algoritmer kan vi enkelt härleda helt polynom tid approximation system (FPTAS).
REF presenterade pseudopolynomalgoritmer för flera specialfall av det disjunktivt knapsack problemet som huvudsakligen baseras på en graf representation: träd, grafer med avgränsad trädbredd och ackord diagram.
The Knapsack Problem with Conflict Graphs
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}