Record link: 
http://hdl.handle.net/20.500.12708/188985
-
Title: 
The Parameterized Complexity of Network Microaggregation
en
Citation: 
Blažej, V., Ganian, R., Knop, D., Pokorný, J., Schierreich, Š., & Simonov, K. (2023). The Parameterized Complexity of Network Microaggregation. In B. Williams, Y. Chen, & J. Neville (Eds.), Proceedings of the 37th AAAI Conference on Artificial Intelligence (pp. 6262–6270). AAAI Press. https://doi.org/10.1609/aaai.v37i5.25771
-
Publisher DOI: 
10.1609/aaai.v37i5.25771
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Blažej, Václav 
Ganian, Robert 
Knop, Dusan 
Pokorný, Jan 
Schierreich, Šimon 
Simonov, Kirill 
-
Organisational Unit: 
E192 - Institut für Logic and Computation 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
Proceedings of the 37th AAAI Conference on Artificial Intelligence 
-
ISBN: 
978-1-57735-880-0
-
Volume: 
37, 5
-
Date (published): 
2023
-
Event name: 
Thirty-Seventh AAAI Conference on Artificial Intelligence 
en
Event date: 
7-Feb-2023 - 14-Feb-2023
-
Event place: 
Washington DC, United States of America (the)
-
Number of Pages: 
9
-
Publisher: 
AAAI Press, Washington DC
-
Peer reviewed: 
Yes
-
Keywords: 
Network Microaggregation; Parameterized Complexity
en
Abstract: 
Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

129
checked on Nov 23, 2023

Google ScholarTM

Check