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 -