Cardinality constrained and multicriteria (multi)cut problems

DOI10.1016/j.jda.2008.04.004zbMath1168.68388OpenAlexW1965106414MaRDI QIDQ1013079

Frédéric Roupin, Cédric Bentz, Marie-Christine Costa, Nicolas Derhy

Publication date: 16 April 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.04.004

zbMATH Keywords

dynamic programmingmulticriteria optimizationmulticut\(\mathcal{NP}\)-hardnesscardinality constraint

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Robust combinatorial optimization with variable cost uncertainty ⋮ A randomized algorithm with local search for containment of pandemic disease spread ⋮ An FPT algorithm for planar multicuts with sources and sinks on the outer face

Cites Work

• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Minimal multicut and maximal integer multiflow: a survey
• Some simplified NP-complete graph problems
• Cardinality constrained minimum cut problems: complexity and algorithms.
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Multicriteria global minimum cuts
• The Complexity of Multiterminal Cuts

This page was built for publication: Cardinality constrained and multicriteria (multi)cut problems