• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
Bazgan-Degree.pdf (461.4Kb)
Type
Article accepté pour publication ou publié
Date
2021
Journal name
Theoretical Computer Science
Volume
873
Publisher
Elsevier
Pages
1-15
Publication identifier
10.1016/j.tcs.2021.04.020
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Laboratoire 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 algorithm

Related items

Showing items related by title and author.

  • Thumbnail
    How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations 
    Bazgan, Cristina; Cazals, Pierre; Chlebíková, Janka (2020) Communication / Conférence
  • Thumbnail
    Structural and algorithmic properties of 2-community structures 
    Bazgan, Cristina; Chlebíková, Janka; Pontoizeau, Thomas (2018) Article accepté pour publication ou publié
  • Thumbnail
    Graphs without a partition into two proportionally dense subgraphs 
    Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément (2020) Article accepté pour publication ou publié
  • Thumbnail
    New Insight into 2-Community Structures in Graphs with Applications in Social Networks 
    Bazgan, Cristina; Chlebíková, Janka; Pontoizeau, Thomas (2015) Communication / Conférence
  • Thumbnail
    Proportionally dense subgraph of maximum size: Complexity and approximation 
    Bazgan, Cristina; Chlebíková, Janka; Dallard, Clément; Pontoizeau, Thomas (2019) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo