Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/66317
Title: Approximate association via dissociation
Authors: You, J 
Wang, J
Cao, Y 
Keywords: Association set (cluster vertex deletion)
Dissociation set
Cluster graph
Modular decomposition
Triangle-free graph
Issue Date: 2017
Publisher: North-Holland
Source: Discrete applied mathematics, 11 Mar. 2017, v. 219, p. 202-209 How to cite?
Journal: Discrete applied mathematics 
Abstract: A vertex set X of a graph G is an association set if each component of G - X is a clique, and a dissociation set if each of these cliques has only one or two vertices. We observe some special structures and show that if none of them exists, then the minimum association set problem can be reduced to the minimum weighted dissociation set problem. This yields the first nontrivial approximation algorithm for the association set problem, with approximation ratio 2.5. The reduction is based on a combinatorial study of modular decomposition of graphs free of these special structures. Further, a novel algorithmic use of modular decomposition enables us to implement our algorithm in O(mn + n(2)) time.
URI: http://hdl.handle.net/10397/66317
ISSN: 0166-218X
DOI: 10.1016/j.dam.2016.11.007
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

3
Last Week
0
Last month
Citations as of Aug 18, 2018

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
Citations as of Aug 14, 2018

Page view(s)

34
Last Week
0
Last month
Citations as of Aug 13, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.