Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1206.90141
Gassner, Elisabeth
The partial inverse minimum cut problem with $L_1$-norm is strongly NP-hard. (English)
[J] RAIRO, Oper. Res. 44, No. 3, 241-249 (2010). ISSN 0399-0559; ISSN 1290-3868/e

Summary: The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted $L_{1}$-norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of {\it X. Yang} [RAIRO, Oper. Res. 35, No.~1, 117--126 (2001; Zbl 0993.90068)] for this problem with additional bound constraints is not correct.

MSC 2000:: *90C27 Combinatorial programming
90C60 Abstract computational complexity for math. programming problems
68Q25 Analysis of algorithms and problem complexity

Keywords: partial inverse minimum cut problem

Citations: Zbl 0993.90068

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]