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

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)

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

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Cardinality constrained minimum cut problems: complexity and algorithms.
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• 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)

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

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)