dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Requile, Clement | |
dc.contributor.author | Thilikos, Dimitrios M. | |
dc.date.accessioned | 2016-06-02T11:06:34Z | |
dc.date.available | 2016-06-02T11:06:34Z | |
dc.date.issued | 2015 | |
dc.identifier.isbn | 978-3-939897-92-7 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/1956/12052 | |
dc.description.abstract | The Plane Diameter Completion problem asks, given a plane graph G and a positive integer d, if it is a spanning subgraph of a plane graph H that has diameter at most d. We examine two variants of this problem where the input comes with another parameter k. In the first variant, called BPDC, k upper bounds the total number of edges to be added and in the second, called BFPDC, k upper bounds the number of additional edges per face. We prove that both problems are NP-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when k=1 on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in O(n^{3})+2^{2^{O((kd)^2\log d)}} * n steps. | en_US |
dc.language.iso | eng | eng |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Attribution CC BY 3.0 | eng |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0 | eng |
dc.subject | Planar graphs | eng |
dc.subject | graph modification problems | eng |
dc.subject | parameterized algorithms | eng |
dc.subject | dynamic programming | eng |
dc.subject | branchwidth | eng |
dc.title | Variants of plane diameter completion | en_US |
dc.type | Peer reviewed | |
dc.type | Journal article | |
dc.date.updated | 2016-04-07T06:52:53Z | |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Petr A. Golovach, Clément Requilé, and Dimitrios M. Thilikos | en_US |
dc.identifier.doi | https://doi.org/10.4230/lipics.ipec.2015.30 | |
dc.identifier.cristin | 1320305 | |
dc.source.journal | Leibniz International Proceedings in Informatics | |
dc.source.pagenumber | 30-42 | |
dc.subject.nsi | VDP::Matematikk og Naturvitenskap: 400 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics 2015, 43:30-42 | |
dc.source.volume | 43 | |