Algorithm research for prize-collecting dominating set problem on special graph
- 20 October 2022
- conference paper
- Published by SPIE-Intl Soc Optical Eng
- Vol. 12350, 685-691
Abstract
The prize-collecting dominating set (PCDS) problem is the generalization of the minimum dominating set (MDS) problem. The MDS problem requires a dominating set in a given graph, namely a subset of vertexes. Any vertex in the graph belongs to the closed neighborhood of the subset of vertexes, where the subset of vertexes with the smallest cardinality is the MDS. In the PCDS problem: given an undirected graph, its vertex setV has nonnegative weighting functionω and nonnegative penalty functionπ . Finding a vertex subset D⊂V, for vertexes do not belong to the closed neighborhood of D , we need to pay penalties for them. The objective of this issue is to minimize the sum of weights and penalties. As we all know that the MDS problem is NP-hard in general graph, obviously, PCDS problem is NP-hard, too., In certain cases, the PCDS problem can achieve better results than the MDS problem, which has a certain value in practical applications such as facility location and logistics management. Whether the problem is limited to a special graph will get useful structural characterization and corresponding algorithm results is considered, designed polynomial time exact algorithm on the star and according to the r -LMP approximation algorithm, designed the 2-LMP approximation algorithm on the path and cycle.Keywords
This publication has 11 references indexed in Scilit:
- Covering problems in edge- and node-weighted graphsDiscrete Optimization, 2016
- Hybrid metaheuristic algorithms for minimum weight dominating setApplied Soft Computing, 2013
- A Unified Approach to Approximating Partial Covering ProblemsAlgorithmica, 2009
- Approximation algorithms for partially covering with edgesTheoretical Computer Science, 2008
- Graph-Theoretic Concepts in Computer Science2005
- Analysis of a greedy heuristic for finding small dominating sets in graphsInformation Processing Letters, 1991
- Dominating sets for split and bipartite graphsInformation Processing Letters, 1984
- Optimum domination in weighted treesInformation Processing Letters, 1978
- Graph Theory with Applications1976
- A linear algorithm for the domination number of a treeInformation Processing Letters, 1975