Improved Upper and Lower Bound Heuristics for Degree Anonymization in Social Networks

Sepp Hartung, Clemens Hoffmann, André Nichterlein

Motivated by a strongly growing interest in anonymizing social network data, we investigate the NP-hard Degree Anonymization problem: given an undirected graph, the task is to add…