Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/36296
Title: Edge deletion problems : branching facilitated by modular decomposition
Authors: Liu, YL
Wang, JX
You, J
Chen, JE
Cao, YX 
Keywords: Graph modification problems
Edge deletion problems
Chain graphs
Trivially perfect graphs
Modular decomposition
Branching
Issue Date: 2015
Publisher: Elsevier
Source: Theoretical computer science, 2015, v. 573, p. 63-70 How to cite?
Journal: Theoretical computer science 
Abstract: Edge deletion problems ask for a minimum set of edges whose deletion makes a graph have a certain property. When this property can be characterized by a finite set of forbidden induced subgraphs, the problem can be solved in fixed-parameter time by a naive bounded search tree algorithm. Sometimes deleting an edge to break an erstwhile forbidden induced subgraph might introduce new ones, which may involve the neighbors of the original forbidden induced subgraph. Therefore, in considering possible ways to break a forbidden induced subgraph one naturally takes its neighborhood into consideration. This observation easily yields more efficient branching rules, but a naive implementation will require too many tedious case analyses. Here we take advantage of modular decomposition, which allows us to focus on far simpler quotient graphs instead of the original graphs. They together yield simple improved algorithms for the edge deletion problems to chain graphs and trivially perfect graphs.
URI: http://hdl.handle.net/10397/36296
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2015.01.049
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

4
Last Week
0
Last month
Citations as of Feb 25, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
Citations as of Jun 22, 2017

Page view(s)

31
Last Week
2
Last month
Checked on Jun 25, 2017

Google ScholarTM

Check

Altmetric



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