Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width

被引：0
作者：
Frank Gurski
Carolin Rehs
机构：
[1] University of Düsseldorf,Institute of Computer Science, Algorithmics for Hard Problems Group
来源：
Mathematical Methods of Operations Research | 2019年 / 89卷
关键词：
Knapsack problem; Forcing graph; Conflict graph; Clique-width; 05C85; 90C39; 05C69;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The 0–1-knapsack problem is a well-known NP-hard problem in combinatorial optimization. We consider the extensions to the knapsack problem with conflict graph (KCG) and the knapsack problem with forcing graph (KFG). KCG has first been introduced by Yamada et al. and represents incompatibilities between items of the knapsack instance. KFG has been introduced by Pferschy and Schauer and represents the necessity of items for other items. Within this paper we provide pseudo-polynomial solutions for KCG and KFG with co-graphs as conflict and forcing graphs and extend these solutions to conflict and forcing graphs of bounded clique-width. Our solutions are based on dynamic programming using the tree-structure representing the conflict graph and the forcing graph. Further we conclude fully polynomial time approximation schemes for KCG on conflict graphs of bounded clique-width and KFG on forcing graphs of bounded clique-width. This generalizes the known results for conflict graphs and forcing graphs of bounded tree-width of Pferschy and Schauer.
引用
收藏
页码：411 / 432
页数：21
相关论文
共 34 条
  • [1] Corneil DG(2005)On the relationship between clique-width and treewidth SIAM J Comput 4 825-847
  • [2] Rotics U(1981)Complement reducible graphs Discrete Appl Math 3 163-174
  • [3] Corneil DG(1985)A linear recognition algorithm for cographs SIAM J Comput 14 926-934
  • [4] Lerchs H(2000)Upper bounds to the clique width of graphs Discrete Appl Math 101 77-114
  • [5] Stewart-Burlingham L(2000)Linear time solvable optimization problems on graphs of bounded clique-width Theory Comput Syst 33 125-150
  • [6] Corneil DG(2003)Deciding clique-width for graphs of bounded tree-width J Graph Algorithms Appl Special Issue JGAA WADS 2001 7 141-180
  • [7] Perl Y(2005)A simple linear time algorithm for cograph recognition Discrete Appl Math 145 183-197
  • [8] Stewart LK(1975)Fast approximation algorithms for the knapsack and sum of subset problem J ACM 22 463-468
  • [9] Courcelle B(2009)Recent developments on graphs of bounded clique-width Discrete Appl Math 157 2747-2761
  • [10] Olariu S(2006)Approximating clique-width and branch-width J Combin Theory Ser B 96 514-528
1234