Show simple item record

dc.contributor.authorGolovach, Petr
dc.contributor.authorRequile, Clement
dc.contributor.authorThilikos, Dimitrios M.
dc.identifier.citationLeibniz International Proceedings in Informatics 2015, 43:30-42eng
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.publisherDagstuhl Publishingeng
dc.rightsAttribution CC BY 3.0eng
dc.subjectPlanar graphseng
dc.subjectgraph modification problemseng
dc.subjectparameterized algorithmseng
dc.subjectdynamic programmingeng
dc.titleVariants of plane diameter completioneng
dc.typeConference objecteng
dc.rights.holderCopyright Petr A. Golovach, Clément Requilé, and Dimitrios M. Thilikoseng
bora.peerreviewedPeer reviewedeng
dc.type.documentJournal article
noa.nsiVDP::Matematikk og Naturvitenskap: 400eng

Files in this item


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