Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/76414
Title: Unit interval editing is fixed-parameter tractable
Authors: Cao, YX 
Keywords: Graph modification problem
Forbidden induced subgraph
Proper Helly circular-arc graph
(Proper,unit) interval model
(Proper,Helly) arc model
Certifying algorithm
{Claw,S-3, (S)over-bar(3), C-4}-free graph
Issue Date: 2017
Publisher: Academic Press
Source: Information and computation, 2017, v. 253, pt. 1, p. 109-126 How to cite?
Journal: Information and computation 
Abstract: Given a graph G and integers k(1), k(2), and k(3), the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k(1) vertex deletions, k(2) edge deletions, and k(3) edge additions. We give an algorithm solving this problem in time 2(o(klogk)). (n+m), where k := k(1) + k(2) + k(3), and n,m denote respectively the numbers of vertices and edges of G. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed -parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time O(4(k) (n +m)). Another result is an 0 (6(k) . (n +m))-time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time O(6(k) .n(6)).
URI: http://hdl.handle.net/10397/76414
ISSN: 0890-5401
EISSN: 1090-2651
DOI: 10.1016/j.ic.2017.01.008
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

3
Citations as of May 12, 2018

WEB OF SCIENCETM
Citations

1
Last Week
1
Last month
Citations as of May 20, 2018

Page view(s)

3
Citations as of May 21, 2018

Google ScholarTM

Check

Altmetric


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