The partial inverse minimum cut problem withL1-norm is strongly NP-hard

DOI10.1051/RO/2010017zbMath1206.90141OpenAlexW2029899910MaRDI QIDQ3057531

Elisabeth Gassner

Publication date: 24 November 2010

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/44720

zbMATH Keywords

partial inverse minimum cut problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (8)

Algorithm for constraint partial inverse matroid problem with weight increase forbidden ⋮ Algorithms for the partial inverse matroid problem in which weights can only be increased ⋮ Capacitated partial inverse maximum spanning tree under the weighted \(l_{\infty }\)-norm ⋮ Approximation algorithms for capacitated partial inverse maximum spanning tree problem ⋮ Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance ⋮ Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm ⋮ Capacitated partial inverse maximum spanning tree under the weighted Hamming distance ⋮ Partial inverse maximum spanning tree problem under the Chebyshev norm

Cites Work

• Some simplified NP-complete graph problems
• Inverse problem of minimum cuts
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem
• Maximal Flow Through a Network
• Inverse Optimization

This page was built for publication: The partial inverse minimum cut problem withL₁-norm is strongly NP-hard