On the computational complexities of three problems related to a privacy measure for large networks under active attack

DOI10.1016/J.TCS.2018.12.013zbMath1422.68108arXiv1607.01438OpenAlexW2904985925WikidataQ128736021 ScholiaQ128736021MaRDI QIDQ2419112

Tanima Chatterjee, Venkatkumar Srinivasan, Nasim Mobasheri, Ismael González Yero, Bhaskar Das Gupta

Publication date: 29 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.01438

zbMATH Keywords

computational complexitysocial networksactive attackprivacy measure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data encryption (aspects in computer science) (68P25)

Related Items (2)

\((k, l)\)-anonymity in wheel-related social graphs measured on the base of \(k\)-metric antidimension ⋮ K-metric antidimension of some generalized Petersen graphs

Uses Software

• PrivateLR

Cites Work

• Unnamed Item
• Unnamed Item
• On communication protocols that compute almost privately
• Approximation algorithms for combinatorial problems
• \(k\)-metric antidimension: a privacy measure for social graphs
• On the complexity of \(k\)-metric antidimension problem and the size of \(k\)-antiresolving sets in random graphs
• A threshold of ln n for approximating set cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Privacy and Communication Complexity
• Privacy, additional information and communication
• Differential Privacy

This page was built for publication: On the computational complexities of three problems related to a privacy measure for large networks under active attack