|
 
|
[BCD09a] Cardinality constrained and multicriteria (multi)cut problems
Revue Internationale avec comité de lecture : Journal Journal of Discrete Algorithms, vol. 7(1), pp. 102-111, 2009, (doi:10.1016/j.jda.2008.04.004)
motcle:
Résumé:
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,...,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 jth criterion, is at most Bj, for 1<=j<=R. We prove
this problem to be NP-complete in paths and cycles even if R = 2. When R=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 NP-complete if k=1 and that, for arbitrary k, it remains strongly NP-complete in directed stars but can be solved by (polynomial) dynamic programming algorithms in paths and cycles. For k = 1, we also prove that
R-CriMultiCut is strongly NP-complete in planar bipartite graphs and remains
NP-complete in K_{2,d} even for R = 2.
Commentaires:
note
Equipe:
oc
Collaboration:
LIPN
BibTeX
| @article { | |||
| BCD09a, | |||
| title | = | "{Cardinality constrained and multicriteria (multi)cut problems}", | |
| author | = | "C. Bentz and M.-C. Costa and N. Derhy and F. Roupin", | |
| journal | = | "Journal of Discrete Algorithms", | |
| year | = | 2009, | |
| volume | = | 7, | |
| number | = | 1, | |
| pages | = | "102-111", | |
| note | = | "{note}", | |
| doi | = | "10.1016/j.jda.2008.04.004", | |
| } | |||
