The Library
A subexponential parameterized algorithm for proper interval completion
Tools
Bliznets, Ivan, Fomin, Fedor V., Pilipczuk, Marcin and Pilipczuk, Michał (2014) A subexponential parameterized algorithm for proper interval completion. In: Wagner , Dorothea and Schulz , Andreas S., (eds.) Algorithms : ESA 2014 : Proceedings of 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Lecture Notes in Computer Science (Volume 8737). Berlin ; London: Springer-Verlag, pp. 173-184. ISBN 9783662447765
|
PDF
WRAP_1371795-cs-270115-proper-interval-completion.pdf - Accepted Version - Requires a PDF viewer. Download (493Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-44777-2_15
Abstract
In the Proper Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999], who showed an algorithm for the problem working in O(16k⋅(n+m)) time. In this paper we present an algorithm with running time kO(k2/3)+O(nm(kn+m)), which is the first subexponential parameterized algorithm for Proper Interval Completion.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Parameter estimation, Computational complexity, Computer algorithms | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Publisher: | Springer-Verlag | ||||
Place of Publication: | Berlin ; London | ||||
ISBN: | 9783662447765 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Algorithms : ESA 2014 : Proceedings of 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014 | ||||
Editor: | Wagner , Dorothea and Schulz , Andreas S. | ||||
Official Date: | 2014 | ||||
Dates: |
|
||||
Number: | Volume 8737 | ||||
Page Range: | pp. 173-184 | ||||
DOI: | 10.1007/978-3-662-44777-2_15 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 28 March 2016 | ||||
Date of first compliant Open Access: | 28 March 2016 | ||||
Funder: | Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC), Russia (Federation) | ||||
Grant number: | 267959 (ERC), |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year