Cardinality constrained and multicriteria (multi)cut problems

DOI10.1016/J.JDA.2008.04.004MaRDI QIDQ1013079zbMATH OpenOpenAlexFDO

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

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

\(\mathcal{NP}\)-hardnesscardinality constraintdynamic programmingmulticriteria optimizationmulticut

Mathematics Subject Classification ID

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

Recommendations

• Cardinality constrained minimum cut problems: complexity and algorithms.
• Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
• Decision Procedures for Multisets with Cardinality Constraints
• Cardinality constrained combinatorial optimization: complexity and polyhedra
• On cutting planes for cardinality-constrained linear programs
• scientific article; zbMATH DE number 7753414
• Optimization problems with cardinality constraints
• Constraint qualifications and optimality conditions for optimization problems with cardinality constraints
• Branch-and-cut for complementarity and cardinality constrained linear programs

Cites work

• Cardinality constrained minimum cut problems: complexity and algorithms.
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimal multicut and maximal integer multiflow: a survey
• Multicriteria global minimum cuts
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Some simplified NP-complete graph problems
• The Complexity of Multiterminal Cuts

Cited in

(9)

• Cardinality constrained minimum cut problems: complexity and algorithms.
• An FPT algorithm for planar multicuts with sources and sinks on the outer face
• A constraint programming approach to cutset problems
• Multicriteria global minimum cuts
• CUT: A Multicriteria Approach for Concavifiable Preferences
• Robust combinatorial optimization with variable cost uncertainty
• A randomized algorithm with local search for containment of pandemic disease spread
• Algorithms and Computation
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1013079)