Show simple item record

How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBazgan, Cristina
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorCazals, Pierre
dc.contributor.authorChlebíková, Janka
dc.date.accessioned2021-11-26T13:51:03Z
dc.date.available2021-11-26T13:51:03Z
dc.date.issued2020
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22264
dc.language.isoenen
dc.subjectGraphen
dc.subject.ddc004en
dc.titleHow to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotationsen
dc.typeCommunication / Conférence
dc.description.abstractenA graph is k-degree-anonymous if for each vertex there are at least k−1 other vertices of the same degree in the graph. Min Anonymous-Edge-Rotation asks for a given graph G and a positive integer k to find a minimum number of edge rotations that transform G into a k-degree-anonymous graph. In this paper, we establish sufficient conditions for an input graph and k ensuring that a solution for the problem exists. We also prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k=n/3 , where n is the order of a graph. On the positive side, we argue that under some constraints on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Moreover, we show that the problem is solvable in polynomial time for any graph when k=n and for trees when k=θ(n) .en
dc.identifier.citationpages242-256en
dc.relation.ispartoftitleCombinatorial Optimization and Applicationsen
dc.relation.ispartofeditorWu, Weili
dc.relation.ispartofeditorZhang, Zhongnan
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpages834en
dc.relation.ispartofurl10.1007/978-3-030-64843-5en
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-030-64842-8en
dc.relation.conftitle14th International Conference, COCOA 2020en
dc.relation.confdate2020-12
dc.relation.confcityDallasen
dc.relation.confcountryUnited Statesen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-64843-5_17en
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2021-11-26T13:47:59Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
HowToGetADegree-Anonymous.pdf
Size:
370.7Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record