Cardinality constrained minimum cut problems: complexity and algorithms.

DOI10.1016/S0166-218X(03)00358-5zbMath1100.90038OpenAlexW1966902774MaRDI QIDQ1427809

Francesco Maffioli, Matthias Ehrgott, Maurizio Bruglieri

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00358-5

zbMATH Keywords

Semidefinite programmingComputational complexity\(k\)-cardinality minimum cutCardinalityconstrained combinatorial optimizationCut problems

Mathematics Subject Classification ID

Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (8)

The cardinality constrained inverse center location problems on tree networks with edge length augmentation ⋮ On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems ⋮ Constrained Graph Partitioning via Matrix Differential Equations ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ Approximation algorithms for the bi-criteria weighted MAX-CUT problem ⋮ Unnamed Item ⋮ Cardinality constrained and multicriteria (multi)cut problems

Uses Software

• CSDP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• An efficient algorithm for the minimum capacity cut problem
• Inertia characteristics of self-adjoint matrix polynomials
• Constructing a perfect matching is in random NC
• The image of weighted combinatorial problems
• Some simplified NP-complete graph problems
• Integer programming approaches to facilities layout models with forbidden areas
• On the computation of pfaffians
• The \(k\)-cardinality assignment problem
• Semidefinite programming in combinatorial optimization
• Heuristics for cardinality constrained portfolio optimization
• Approximation algorithms for minimum \(K\)-cut
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Finding k Cuts within Twice the Optimal
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A simple min-cut algorithm
• CSDP, A C library for semidefinite programming
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Systems of distinct representatives and linear algebra
• Handbook of semidefinite programming. Theory, algorithms, and applications

This page was built for publication: Cardinality constrained minimum cut problems: complexity and algorithms.