Approximation of knapsack problems with conflict and forcing graphs
From MaRDI portal
Publication:2012887
DOI10.1007/s10878-016-0035-7zbMath1376.90052OpenAlexW2410078569WikidataQ59607346 ScholiaQ59607346MaRDI QIDQ2012887
Joachim Schauer, Ulrich Pferschy
Publication date: 3 August 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: http://link.springer.com/10.1007/s10878-016-0035-7
Related Items (19)
The knapsack problem with special neighbor constraints ⋮ Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games ⋮ Fair Packing of Independent Sets ⋮ Approximations for restrictions of the budgeted and generalized maximum coverage problems ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ A threshold search based memetic algorithm for the disjunctively constrained knapsack problem ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ The knapsack problem with forfeit sets ⋮ Responsive strategic oscillation for solving the disjunctively constrained knapsack problem ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Parameterized complexity of conflict-free set cover ⋮ Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width ⋮ Counting and enumerating independent sets with applications to combinatorial optimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The minimum cost perfect matching problem with conflict pair constraints
- The maximum flow problem with disjunctive constraints
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- The minimum spanning tree problem with conflict constraints and its variations
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Paths, trees and matchings under disjunctive constraints
- Maximum weight independent sets in hole- and co-chair-free graphs
- Scheduling with conflicts: Online and offline algorithms
- Decomposition by clique separators
- Modular decomposition and transitive orientation
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Listing all potential maximal cliques of a graph
- Finding a maximum induced matching in weakly chordal graphs
- Optimizing weakly triangulated graphs
- Algorithms for weakly triangulated graphs
- Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
- Approximation schemes for a class of subset selection problems
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- An algorithm for the disjunctively constrained knapsack problem
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- Algorithms for the Bin Packing Problem with Conflicts
- Improved algorithms for weakly chordal graphs
- Finding Induced Subgraphs via Minimal Triangulations
- The Knapsack Problem with Conflict Graphs
- A Fast Large Neighborhood Search for Disjunctively Constrained Knapsack Problems
- Independent Set in P5-Free Graphs in Polynomial Time
- Transitiv orientierbare Graphen
- Independent Sets of Maximum Weight in Apple-Free Graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
This page was built for publication: Approximation of knapsack problems with conflict and forcing graphs
