|
Abstract : |
This work is motivated by the problem of placing pressure meters in fluid networks. The problem is formally defined in graph-theoretic terms as follows. Given a graph, find a cotree (complement of a tree) incident upon the minimum number of vertices. We show that this problem is NP-hard and MAX SNP-hard. We design an algorithm with an approximation factor of 2 + ffl for this problem. This approximation bound comes from the analysis of a local search heuristic, a common practical optimization technique that does not often allow formal worst case analysis. The algorithm is made very efficient by finding restrictive definitions of the local neighborhoods to be searched. We also exhibit a PTAS for this problem when the input is restricted to planar graphs. Although we are motivated by water distribution networks, the algorithms apply to any system that can be formulated as a network, in which Kirchoff's laws are valid and a bijective relation exists between the flow variable and the effort variable, like circuits and electrical networks., |
