Algorithm research for prize-collecting dominating set problem on special graph

Yuan Gao; Zhibin Chen

doi:10.1117/12.2652680

20 October 2022 Algorithm research for prize-collecting dominating set problem on special graph

Yuan Gao, Zhibin Chen

Proceedings Volume 12350, 6th International Workshop on Advanced Algorithms and Control Engineering (IWAACE 2022); 123502O (2022) https://doi.org/10.1117/12.2652680
Event: 6th International Workshop on Advanced Algorithms and Control Engineering (IWAACE 2022), 2022, Qingdao, China

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.

Citation Download Citation

Yuan Gao and Zhibin Chen "Algorithm research for prize-collecting dominating set problem on special graph ", Proc. SPIE 12350, 6th International Workshop on Advanced Algorithms and Control Engineering (IWAACE 2022), 123502O (20 October 2022); https://doi.org/10.1117/12.2652680

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available