Approximation of knapsack problems with conflict and forcing graphs
type: Item
instance of: scholarly article
title: Approximation of knapsack problems with conflict and forcing graphs
zbMATH Open document ID: 1376.90052
author: Ulrich Pferschy
author: Joachim Schauer
published in: Journal of Combinatorial Optimization
publication date: 2017-08-03T00:00:00Z
full work available at URL: s10878-016-0035-7
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6756023
zbMATH Keywords: knapsack problem
zbMATH Keywords: conflict graph
zbMATH Keywords: weakly chordal graph
zbMATH Keywords: planar graph
zbMATH Keywords: graph decomposition
Wikidata QID: Q59607346
MaRDI profile type: Publication
OpenAlex ID: W2410078569
cites work: Q4944976
cites work: Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: Listing all potential maximal cliques of a graph
cites work: Maximum weight independent sets in hole- and co-chair-free graphs
cites work: Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs''
cites work: On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
cites work: Independent Sets of Maximum Weight in Apple-Free Graphs
cites work: Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Paths, trees and matchings under disjunctive constraints
cites work: Transitiv orientierbare Graphen
cites work: Q5315023
cites work: Scheduling with conflicts: Online and offline algorithms
cites work: Finding Induced Subgraphs via Minimal Triangulations
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Optimizing weakly triangulated graphs
cites work: Improved algorithms for weakly chordal graphs
cites work: An algorithm for the disjunctively constrained knapsack problem
cites work: A Fast Large Neighborhood Search for Disjunctively Constrained Knapsack Problems
cites work: Q4821303
cites work: Independent Set in P5-Free Graphs in Polynomial Time
cites work: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
cites work: Modular decomposition and transitive orientation
cites work: The minimum cost perfect matching problem with conflict pair constraints
cites work: Algorithms for the bin packing problem with conflicts
cites work: The Knapsack Problem with Conflict Graphs
cites work: The maximum flow problem with disjunctive constraints
cites work: Approximation schemes for a class of subset selection problems
cites work: Algorithms for weakly triangulated graphs
cites work: Decomposition by clique separators
cites work: Q3686753
cites work: The minimum spanning tree problem with conflict constraints and its variations
DOI: 10.1007/S10878-016-0035-7
description: scientific article; zbMATH DE number 6756023