Exact Algorithms for Dominating Set
- PDF / 241,910 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 44 Downloads / 256 Views
E
Exact Algorithms for Dominating Set
8. Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. In: Technical report, Graduate School of Industrial Administration. Carnegie-Mellon University, Pittsburgh (1976) 9. Czumaj, A., Lingas, A.: On approximability of the minimumcost k-connected spanning subgraph problem. In: Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 281–290 10. Czumaj, A., Lingas, A.: Approximation schemes for minimumcost k-connectivity problems in geometric graphs. In: Gonzalez, T.F. (eds.) Handbook of Approximation Algorithms and Metaheuristics. CRC Press, Boca Raton (2007) 11. Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proc. 8th Annual ACM Symposium on Theory of Computing, 1976, pp. 10–22 12. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, Chichester (1985) 13. Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298–1309 (1999) 14. Papadimitriou, C.H.: Euclidean TSP is NP-complete. Theor. Comput. Sci. 4, 237–244 (1977) 15. Rao, S.B., Smith, W.D.: Approximating geometrical graphs via “spanners” and “banyans”. In: Proc. 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 540–550 16. Remy, J., Steger, A.: A quasi-polynomial time approximation scheme for minimum weight triangulation. In: Proc. 38th Annual ACM Symposium on Theory of Computing, 2006 17. Trevisan, L.: When Hamming meets Euclid: the approximability of geometric TSP and Steiner Tree. SIAM J. Comput. 30(2), 475– 485 (2000)
Exact Algorithms for Dominating Set 2005; Fomin, Grandoni, Kratsch DIETER KRATSCH UFM MIM – LITA, Paul Verlaine University, Metz, France Keywords and Synonyms Connected dominating set Problem Definition The dominating set problem is a classical NP-hard optimization problem which fits into the broader class of covering problems. Hundreds of papers have been written on this problem that has a natural motivation in facility location. Definition 1 For a given undirected, simple graph G = (V ; E) a subset of vertices D V is called a dominating set if every vertex u 2 V D has a neighbor in D. The
minimum dominating set (MDS) problem is to find a minimum dominating set of G, i. e. a dominating set of G of minimum cardinality. Problem 1 (MDS) Input: Undirected simple graph G = (V ; E). Output: A minimum dominating set D of G. Various modifications of the dominating set problem are of interest, some of them obtained by putting additional constraints on the dominating set such as, for example, requesting it to be an independent set or to be connected. In graph theory there is a huge literature on domination dealing with the problem and its many modifications (see e. g.[9]). In graph algorithms the MDS problem and some of its modifications like Independent Dominating Set and Connected Do
Data Loading...
