Show simple item record

hal.structure.identifier
dc.contributor.authorKhoshkhah, Kaveh
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKhosravian Ghadikolaei, Mehdi
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
hal.structure.identifier
dc.contributor.authorTheis, Dirk Oliver
dc.date.accessioned2019-07-16T10:55:41Z
dc.date.available2019-07-16T10:55:41Z
dc.date.issued2019
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19245
dc.language.isoenen
dc.subjectComputational complexityen
dc.subjectParameterized complexityen
dc.subjectApproximation algorithmsen
dc.subjectGraphsen
dc.subjectExtended solutionen
dc.subjectSpanning Star Foresten
dc.subject.ddc005en
dc.titleComplexity and approximability of extended Spanning Star Forest problems in general and complete graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA solution extension problem consists in an instance and a partial feasible solution which is given in advance and the goal is to extend this partial solution to a feasible one. Many well-known problems like Coloring Extension Problems, Traveling Salesman Problem and Routing problems, have been studied in this framework. In this paper, we focus on the edge-weighted spanning star forest problem for both minimization and maximization versions. The goal here is to find a vertex partition of an edge-weighted graph into disjoint non-trivial stars and the value of a solution is given by the sum of the edge-weights of the stars. We propose NP-hardness, parameterized complexity, positive and negative approximation results.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol775en
dc.relation.isversionofjnldate2019-07
dc.relation.isversionofjnlpages1-15en
dc.relation.isversionofdoi10.1016/j.tcs.2018.11.025en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-07-16T10:52:47Z
hal.identifierhal-02185007*
hal.version1*
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