Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/67165
Title: Approximate association via dissociation
Authors: You, J 
Wang, J
Cao, Y 
Issue Date: 2016
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2016, v. 9941, p. 13-24 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
Abstract: A vertex set X of a graph G is an association set if each component of G − X is a clique, or a dissociation set if each component of G − X is a single vertex or a single edge. Interestingly, G − X is then precisely a graph containing no induced P3’s or containing no P3’s, respectively. 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 is 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 this approach in O(mn + n2) time.
Description: 42nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2016, Istanbul, Turkey, 22-24 June 2016
URI: http://hdl.handle.net/10397/67165
ISBN: 9783662535356
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/978-3-662-53536-3_2
Appears in Collections:Conference Paper

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

Page view(s)

17
Last Week
1
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



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