hal.structure.identifier Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE] dc.contributor.author Bazgan, Cristina hal.structure.identifier Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE] dc.contributor.author Cazals, Pierre dc.contributor.author Chlebíková, Janka dc.date.accessioned 2021-11-26T13:51:03Z dc.date.available 2021-11-26T13:51:03Z dc.date.issued 2020 dc.identifier.uri https://basepub.dauphine.psl.eu/handle/123456789/22264 dc.language.iso en en dc.subject Graph en dc.subject.ddc 004 en dc.title How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations en dc.type Communication / Conférence dc.description.abstracten A 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.citationpages 242-256 en dc.relation.ispartoftitle Combinatorial Optimization and Applications en dc.relation.ispartofeditor Wu, Weili dc.relation.ispartofeditor Zhang, Zhongnan dc.relation.ispartofpublname Springer en dc.relation.ispartofpages 834 en dc.relation.ispartofurl 10.1007/978-3-030-64843-5 en dc.subject.ddclabel Informatique générale en dc.relation.ispartofisbn 978-3-030-64842-8 en dc.relation.conftitle 14th International Conference, COCOA 2020 en dc.relation.confdate 2020-12 dc.relation.confcity Dallas en dc.relation.confcountry United States en dc.relation.forthcoming non en dc.identifier.doi 10.1007/978-3-030-64843-5_17 en dc.description.ssrncandidate non dc.description.halcandidate non en dc.description.readership recherche en dc.description.audience International en dc.relation.Isversionofjnlpeerreviewed non en dc.date.updated 2021-11-26T13:47:59Z hal.author.function aut hal.author.function aut hal.author.function aut
﻿