direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

The Complexity of Degree Anonymization by Vertex Addition

M.Sc. Nimrod Talmon (TU Berlin)

Motivated by applications in privacy-preserving data publishing, we study the problem to make an undirected graph k-anonymous by adding few vertices (together with incident edges). That is, after adding these dummy vertices, for every vertex degree d in the resulting graph, there shall be at least k vertices with degree d. We explore three variants of vertex addition (justified by real-world considerations) and study their (parameterized) computational complexity. We derive mostly (worst-case) intractability results, even for very restricted cases (including trees or bounded-degree graphs) but also obtain a few encouraging fixed-parameter tractability results.

19.06.2014 16:15
Nimrod Talmon
TEL 512

Back to the research colloquium site.

Zusatzinformationen / Extras