Show simple item record

dc.contributor.authorCohen, Nathann
dc.contributor.authorGonçalves, Daniel
dc.contributor.authorKim, Eun Jung
dc.contributor.authorPaul, Christophe
dc.contributor.authorSau Valls, Ignasi
dc.contributor.authorThilikos, Dimitrios M.
dc.date.accessioned2020-05-27T13:14:33Z
dc.date.available2020-05-27T13:14:33Z
dc.date.issued2017
dc.identifier.issn0022-0000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20787
dc.language.isoenen
dc.subjectDiameter improvementen
dc.subjectOuterplanar graphsen
dc.subjectCompletion problemsen
dc.subjectPolynomial-time algorithmsen
dc.subjectDynamic programmingen
dc.subject.ddc005en
dc.titleA polynomial-time algorithm for Outerplanar Diameter Improvementen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe Outerplanar Diameter Improvement problem asks, given a graph G and an integer D, whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.en
dc.relation.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol89en
dc.relation.isversionofjnldate2017-11
dc.relation.isversionofjnlpages315-327en
dc.relation.isversionofdoi10.1016/j.jcss.2017.05.016en
dc.identifier.urlsitehttps://hal.inria.fr/hal-01592242en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-05-27T13:11:42Z
hal.person.labIds
hal.person.labIds
hal.person.labIds989
hal.person.labIds
hal.person.labIds
hal.person.labIds


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record