Loading...
Please wait, while we are loading the content...
The Complexity of Degree Anonymization by Vertex Addition (2015)
| Content Provider | CiteSeerX |
|---|---|
| Author | Bredereck, Robert Froese, Vincent Nichterlein, Andre Niedermeier, Rolf Talmon, Nimrod |
| Abstract | Motivated by applications in privacy-preserving data publishing, we study the problem of making an undirected graph k-anonymous by adding few vertices (together with some incident edges). That is, after adding these “dummy vertices”, for every vertex degree d appearing 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 intractability results, even for very restricted cases (including trees and bounded-degree graphs) but also obtain some encouraging fixed-parameter tractability results. |
| File Format | |
| Publisher Date | 2015-01-01 |
| Access Restriction | Open |
| Subject Keyword | Degree Anonymization Vertex Additioni Computational Complexity Bounded-degree Graph Vertex Addition Encouraging Fixed-parameter Tractability Result Real-world Consideration Restricted Case Undirected Graph Privacy-preserving Data Publishing Dummy Vertex Vertex Degree Incident Edge Intractability Result |
| Content Type | Text |
