The Library
A subexponential parameterized algorithm for proper interval completion
Tools
Tools
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 > 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 | ||||
| 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
