Please use this identifier to cite or link to this item:
Title: Unit interval editing is fixed-parameter tractable
Authors: Cao, Y 
Issue Date: 2015
Publisher: Springer
Source: In MM Halldórsson, K Iwama, N Kobayashi & B Speckmann (Eds.), Automata, languages, and programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, p. 306-317. Heidelberg: Springer, 2015 How to cite?
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 the problem in 2O(klogk) ·(n+m) time, 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. This 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 best-known algorithm running in time O(6k · n6).
ISBN: 9783662476727 (electronic bk.) (pt. 1)
366247672X (electronic bk.) (pt. 1)
9783662476710 (print) (pt. 1)
9783662476666 (electronic bk.) (pt. 2)
3662476665 (electronic bk.) (pt. 2)
9783662476659 (print) (pt. 2)
DOI: 10.1007/978-3-662-47672-7_25
Appears in Collections:Book Chapter

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

Google ScholarTM



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