Show simple item record

hal.structure.identifier
dc.contributor.authorCohen, Nathann
HAL ID: 5651
ORCID: 0000-0002-3341-3712
hal.structure.identifier
dc.contributor.authorGonçalves, Daniel
HAL ID: 7100
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
hal.structure.identifier
dc.contributor.authorPaul, Christophe
HAL ID: 4726
hal.structure.identifier
dc.contributor.authorSau Valls, Ignasi
HAL ID: 7331
ORCID: 0000-0002-8981-9287
hal.structure.identifier
dc.contributor.authorThilikos, Dimitrios M.
HAL ID: 178742
ORCID: 0000-0003-0470-1800
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.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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