Algorithms for graphs with small octopus |
| |
Institution: | 1. Department of Informatics, University of Bergen, N-5020 Bergen, Norway;2. Laboratoire d''Informatique Théorique et Appliquée, Université de Metz, 57045 Metz Cedex 01, France;3. School of Computing, University of Leeds, Leeds, LS2 9JT, UK |
| |
Abstract: | 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 finding 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 efficient 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(n7d+2) time algorithms to compute a minimum cardinality dominating set, respectively, total dominating set for graphs having a d-octopus. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|