کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431363 | 688513 | 2009 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Cardinality constrained and multicriteria (multi)cut problems Cardinality constrained and multicriteria (multi)cut problems](/preview/png/431363.png)
In this paper, we consider multicriteria and cardinality constrained multicut problems. Let G be a graph where each edge is weighted by R positive costs corresponding to R criteria and consider k source–sink pairs of vertices of G and R integers B1,…,BRB1,…,BR. The problem R-CriMultiCut consists in finding a set of edges whose removal leaves no path between the ith source and the ith sink for each i, and whose cost, with respect to the j th criterion, is at most BjBj, for 1⩽j⩽R1⩽j⩽R. We prove this problem to be NPNP-complete in paths and cycles even if R=2R=2. When R=2R=2 and the edge costs of the second criterion are all 1, the problem can be seen as a monocriterion multicut problem subject to a cardinality constraint. In this case, we show that the problem is strongly NPNP-complete if k=1k=1 and that, for arbitrary k , it remains strongly NPNP-complete in directed stars but can be solved by (polynomial) dynamic programming algorithms in paths and cycles. For k=1k=1, we also prove that R-CriMultiCut is strongly NPNP-complete in planar bipartite graphs and remains NPNP-complete in K2,dK2,d even for R=2R=2.
Journal: Journal of Discrete Algorithms - Volume 7, Issue 1, March 2009, Pages 102–111