Algorithms for graphs with small octopus

✍ Scribed by Fedor V. Fomin; Dieter Kratsch; Haiko Müller

• Book ID: 104294228
• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 376 KB
• Volume: 134
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00298-1

✦ Synopsis

A d-octopus of a graph G = (V; E) is a subgraph T = (W; F) of G such that W is a dominating set of G, and T is the union of d (not necessarily disjoint) shortest paths of G that have one endpoint in common. First, we study the complexity of ÿnding and approximating a d-octopus of a graph. Then we show that for some NP-complete graph problems that are hard to approximate in general there are e cient approximation algorithms with worst case performance ratio c • d for some small constant c ¿ 0 (depending on the problem) assuming that the input graph G is given together with a d-octopus of G. For example, there is a linear time algorithm to approximate the bandwidth of a graph within a factor of 8d. Furthermore, the minimum number of subsets in a partition of the vertex set of a graph into clusters of diameter at most k can be approximated in linear time within a factor of 3d (for k = 2) and 2d (for k ¿ 3). Finally, we show that there are O(n 7d+2 ) time algorithms to compute a minimum cardinality dominating set, respectively, total dominating set for graphs having a d-octopus.