Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/75484
Title: Unit interval editing is fixed-parameter tractable
Authors: Cao, Y 
Keywords: (Proper, Helly) arc model
(Proper, unit) interval model
Certifying algorithm
Forbidden induced subgraph
Graph modification problem
Proper Helly circular-arc graph
{Claw, S3,S3‾, C4}-free graph
Issue Date: 2017
Publisher: Academic Press
Source: Information and computation, 2017, v. 253, p. 109-126 How to cite?
Journal: Information and computation 
Abstract: Given a graph G and integers k1, k2, and k3, the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k1 vertex deletions, k2 edge deletions, and k3 edge additions. We give an algorithm solving this problem in time 2O(klog⁡k)⋅(n+m), where k:=k1+k2+k3, 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(4k⋅(n+m)). Another result is an O(6k⋅(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(6k⋅n6).
URI: http://hdl.handle.net/10397/75484
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
Last Week
0
Last month
Citations as of May 28, 2018

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
Citations as of May 28, 2018

Page view(s)

5
Citations as of May 28, 2018

Google ScholarTM

Check

Altmetric


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