Approximating minimum power covers of intersecting families and directed edge-connectivity problems

作者：Nutov Zeev^*

来源：Theoretical Computer Science, 2010, 411(26-28): 2502-2512.

DOI：10.1016/j.tcs.2010.03.009

• Approximation algorithms
• Wireless networks
• Power minimization
• Directed graphs
• Edge-connectivity
• Intersecting families

Given a (directed) graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Let g = (V, epsilon) be a graph with edge costs {c(epsilon) : e is an element of epsilon} and let k be an integer. We consider problems that seek to find a min-power spanning subgraph G of g, that satisfies a prescribed edge-connectivity property. In the Min-Power k-Edge-Outconnected Subgraph problem we are given a root r is an element of V, and require that G contains k pairwise edge-disjoint r upsilon-paths for all upsilon is an element of V - r. In the Min-Power k-Edge-Connected Subgraph problem G is required to be k-edge-connected. For k = 1, these problems are at least as hard as the Set-Cover problem and thus have an Omega(ln vertical bar V vertical bar) approximation threshold. For k = Omega(n(epsilon)), they are unlikely to admit a polylogarithmic approximation ratio [15]. We give approximation algorithms with ratio O(k ln vertical bar V vertical bar). Our algorithms are based on a more general O(ln vertical bar V vertical bar)-approximation algorithm for the problem of finding a min-power directed edge-cover of an intersecting set-family; a set-family F is intersecting if X boolean AND Y, X boolean OR Y is an element of F for any intersecting X, Y is an element of F, and an edge set I covers F if for every X is an element of F there is an edge in I entering X.

• 出版日期2010-6-6