Inapproximability and a polynomially solvable special case of a network improvement problem.

DOI10.1016/S0377-2217(02)00876-7zbMath1045.90011OpenAlexW2056975114MaRDI QIDQ1428068

Zhang, Jianzhong, Xiao-guang Yang, Mao-cheng Cai

Publication date: 14 March 2004

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(02)00876-7

zbMATH Keywords

Shortest pathInapproximabilityNetwork flowsMaximum 3-satisfiability

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)

Related Items

The inverse 1-median problem on tree networks with variable real edge lengths ⋮ The inverse 1-maxian problem with edge length modification ⋮ Reverse 2-median problem on trees ⋮ Complexity of some inverse shortest path lengths problems ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Up- and downgrading the 1-center in a network

Cites Work

• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Finding the Minimum-Cost Maximum Flow in a Series-Parallel Network
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item