Show simple item record

dc.contributor.authorGolovach, Petr
dc.contributor.authorRequile, Clement
dc.contributor.authorThilikos, Dimitrios M.
dc.date.accessioned2016-06-02T11:06:34Z
dc.date.available2016-06-02T11:06:34Z
dc.date.issued2015
dc.identifier.citationLeibniz International Proceedings in Informatics 2015, 43:30-42eng
dc.identifier.urihttp://hdl.handle.net/1956/12052
dc.description.abstractThe 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.eng
dc.language.isoengeng
dc.publisherDagstuhl Publishingeng
dc.rightsAttribution CC BY 3.0eng
dc.rights.urihttp://creativecommons.org/licenses/by/3.0eng
dc.subjectPlanar graphseng
dc.subjectgraph modification problemseng
dc.subjectparameterized algorithmseng
dc.subjectdynamic programmingeng
dc.subjectbranchwidtheng
dc.titleVariants of plane diameter completioneng
dc.typeConference objecteng
dc.date.updated2016-04-07T06:52:53Z
dc.rights.holderCopyright Petr A. Golovach, Clément Requilé, and Dimitrios M. Thilikoseng
dc.type.versionpublishedVersioneng
bora.peerreviewedPeer reviewedeng
dc.type.documentJournal article
dc.identifier.cristinID1320305
dc.identifier.doi10.4230/LIPIcs.IPEC.2015.30eng
noa.nsiVDP::Matematikk og Naturvitenskap: 400eng


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution CC BY 3.0
Except where otherwise noted, this item's license is described as Attribution CC BY 3.0