Algorithms for Placing Monitors in a Flow Network

Autor:	Chin, Francis, Chrobak, Marek, Yan, Li
Rok vydání:	2009
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computational Complexity Computer Science - Discrete Mathematics F.2.2 G.2.2
Druh dokumentu:	Working Paper
Popis:	In the Flow Edge-Monitor Problem, we are given an undirected graph G=(V,E), an integer k > 0 and some unknown circulation \psi on G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge-Monitor Problem is NP-hard, and then we give two approximation algorithms: a 3-approximation algorithm with running time O((m+n)^2) and a 2-approximation algorithm with running time O((m+n)^3), where n = |V| and m=|E|. Comment: 13 pages, 5 figures. Preliminary version appeared in AAIM 2009
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/0908.4309 Zobrazit plný text záznamu View this record from Arxiv