Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Maximum Domination Problem

Miyano, E. and Ono, H.

    We consider new variants of the vertex/edge domination problems on graphs. A vertex is said to dominate itself and its all adjacent vertices, and similarly an edge is said to dominate itself and its all adjacent edges. Given an input graph G = (V, E) and an integer k, the k-Vertex (k-Edge) Maximum Domination (k-MaxVD and k-MaxED, respectively) is to find a subset DV ⊆ V of vertices (resp., DE ⊆ E of edges) with size at most k that maximizes the cardinality of dominated vertices (resp., edges). In this paper, we first show that a simple greedy strategy achieves an approximation ratio of (1 − 1/e) for both k-MaxVD and k-MaxED. Then, we show that this approximation ratio is the best possible for k-MaxVD unless P = NP. We also prove that, for any constant ε > 0, there is no polynomial time 1303/1304+ε approximation algorithm for k-MaxED unless P = NP. However, if k is not larger than the size of the minimum maximal matching, k-MaxED is 3/4-approximable in polynomial time.
Cite as: Miyano, E. and Ono, H. (2011). Maximum Domination Problem. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 55-62
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS