
Degree-anonymization using edge rotations
Bazgan, Cristina; Cazals, Pierre; Chlebíková, Janka (2021), Degree-anonymization using edge rotations, Theoretical Computer Science, 873, p. 1-15. 10.1016/j.tcs.2021.04.020
View/ Open
Type
Article accepté pour publication ou publiéDate
2021Journal name
Theoretical Computer ScienceVolume
873Publisher
Elsevier
Pages
1-15
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Cazals, Pierre
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Chlebíková, Janka
Abstract (EN)
The Min Anonymous-Edge-Rotation problem asks for an input graph G and a positive integer k to find a minimum number of edge rotations that transform G into a graph such that for each vertex there are at least k − 1 other vertices of the same degree (a k-degree-anonymous graph). In this paper, we prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k = n/q, where n is the order of a graph and q any positive integer, q ≥ 3. We argue that under some constrains on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Furthermore, we show that the problem is solvable in polynomial time for any graph when k = n and for trees when k = θ (n). Additionally, we establish sufficient conditions for an input graph and k such that a solution for Min Anonymous-Edge-Rotation exists.Subjects / Keywords
Degree-anonymization; NP-hardness; Approximation algorithmRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Cazals, Pierre; Chlebíková, Janka (2020) Communication / Conférence
-
Bazgan, Cristina; Chlebíková, Janka; Pontoizeau, Thomas (2018) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément (2020) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chlebíková, Janka; Pontoizeau, Thomas (2015) Communication / Conférence
-
Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément; Pontoizeau, Thomas (2019) Article accepté pour publication ou publié