TY - GEN
T1 - The valve location problem in simple network topologies
AU - Bodlaender, Hans L.
AU - Grigoriev, Alexander
AU - Grigorieva, Nadejda V.
AU - Hendriks, Albert
PY - 2008
Y1 - 2008
N2 - To control possible spills in liquid or gas transporting pipe systems, the systems are usually equipped with shutoff valves. In case of an accidental leak these valves separate the system into a number of pieces limiting the spill effect. In this paper, we consider the problem, for a given edge-weighted network representing a pipe system and for a given number of valves, to place the valves in the network in such a way that the maximum possible spill, i.e. the maximum total weight of a piece, is minimized. We show that the problem is NP-hard even if restricted to any of the following settings: (i) for series-parallel graphs and hence for graphs of treewidth two; (ii) if all edge weights equal one. If the network is a simple path, a cycle, or a tree, the problem can be solved in polynomial time. We also give a pseudo-polynomial time algorithm and a fully polynomial approximation scheme for networks of bounded treewidth.
AB - To control possible spills in liquid or gas transporting pipe systems, the systems are usually equipped with shutoff valves. In case of an accidental leak these valves separate the system into a number of pieces limiting the spill effect. In this paper, we consider the problem, for a given edge-weighted network representing a pipe system and for a given number of valves, to place the valves in the network in such a way that the maximum possible spill, i.e. the maximum total weight of a piece, is minimized. We show that the problem is NP-hard even if restricted to any of the following settings: (i) for series-parallel graphs and hence for graphs of treewidth two; (ii) if all edge weights equal one. If the network is a simple path, a cycle, or a tree, the problem can be solved in polynomial time. We also give a pseudo-polynomial time algorithm and a fully polynomial approximation scheme for networks of bounded treewidth.
KW - Binary search
KW - Bounded treewidth
KW - Computational complexity
KW - Dynamic programming
KW - Valve location problem
UR - http://www.scopus.com/inward/record.url?scp=58349103623&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-92248-3_6
DO - 10.1007/978-3-540-92248-3_6
M3 - Conference contribution
AN - SCOPUS:58349103623
SN - 3540922474
SN - 9783540922476
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 55
EP - 65
BT - Graph-Theoretic Concepts in Computer Science - 34th International Workshop, WG 2008, Revised Papers
T2 - 34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008
Y2 - 30 June 2008 through 2 July 2008
ER -