Show simple item record

dc.contributor.authorHanaka, Tesshu
dc.contributor.authorKatsikarelis, Ioannis
dc.contributor.authorLampis, Michael
dc.contributor.authorOtachi, Yota
dc.contributor.authorSikora, Florian
dc.date.accessioned2020-07-22T14:34:55Z
dc.date.available2020-07-22T14:34:55Z
dc.date.issued2018
dc.identifier.issn0178-4617
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20961
dc.language.isoenen
dc.subjectOrientationen
dc.subjectParameterizationen
dc.subjectTreewidthen
dc.subjectSETHen
dc.subject.ddc518en
dc.titleParameterized Orientable Deletionen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenA graph is d-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most d. d-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph G=(V,E), delete the minimum number of vertices to make Gd-orientable. We contribute a number of results that improve the state of the art on this problem.en
dc.relation.isversionofjnlnameAlgorithmica
dc.relation.isversionofjnlvol82en
dc.relation.isversionofjnlissue7en
dc.relation.isversionofjnldate2020-07
dc.relation.isversionofjnlpages1909–1938en
dc.relation.isversionofdoi10.1007/s00453-020-00679-6en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelModèles mathématiques. Algorithmesen
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-07-22T14:31:43Z
hal.person.labIds
hal.person.labIds989
hal.person.labIds989
hal.person.labIds
hal.person.labIds989


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record