TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 19.06.2014

isti-logo

Page Content

to Navigation

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.

Date
Speaker
Location
Language
19.06.2014 16:15
Nimrod Talmon
TEL 512
english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe