کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949903 | 1364262 | 2017 | 17 صفحه PDF | دانلود رایگان |
A set DâV of a graph G=(V,E) is called an open neighborhood locating-dominating set (OLD-set) if (i) NG(v)â©Dâ 0̸ for all vâV, and (ii) NG(u)â©Dâ NG(v)â©D for every pair of distinct vertices u,vâV. Given a graph G=(V,E), the Min OLD-set problem is to find an OLD-set of minimum cardinality. Given a graph G=(V,E) and a positive integer k, the Decide OLD-set problem is to decide whether G has an OLD-set of cardinality at most k. The Decide OLD-set problem is known to NP-complete for general graphs. In this paper we extend the NP-completeness result of the Decide OLD-set problem by showing that it remains NP-complete for bipartite graphs, planar graphs, split graphs and doubly chordal graphs. We prove that the Decide OLD-set problem can be solved in linear time for bounded tree-width graphs. We, then, propose a linear time algorithm for the Min OLD-set problem in trees. We also propose a (2+3lnÎ)-approximation algorithm for the Min OLD-set problem and show that the Min OLD-set problem cannot be approximated within 12(1âϵ)ln|V| for any ϵ>0 unless NPâDTIME(|V|O(loglog|V|)). Finally, we prove that the Min OLD-set problem is APX-complete for bipartite graphs of maximum degree 3.
Journal: Discrete Applied Mathematics - Volume 216, Part 1, 10 January 2017, Pages 290-306