The complexity of degree anonymization by vertex addition
详细信息 查看全文
- 作者：Robert Bredereck1 ; robert.bredereck@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author ; Vincent Froese2 ; vincent.froese@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author ; Sepp Hartung sepp.hartung@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author ; André ; Nichterlein andre.nichterlein@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author ; Rolf Niedermeier rolf.niedermeier@tu-berlin.de" class="auth_mail" title="E-mail the corresponding author ; Nimrod Talmon ; 3 ; nimrodtalmon77@gmail.com" class="auth_mail" title="E-mail the corresponding author
- 关键词：Graph modification ; Degree-constrained editing ; NP-hardness ; Parameterized complexity ; Fixed-parameter tractability ; Kernelization
- 刊名：Theoretical Computer Science
- 出版年：2015
- 出版时间：23 November 2015
- 年：2015
- 卷：607
- 期：part_P1
- 页码：16-34
- 全文大小：627 K
文摘
- •
Degree anonymization by vertex addition is computationally intractable in general.
- •
Posing structural restrictions on the edges connected to the new vertices seems to make the problem even harder.
- •
There are some tractable special cases, for example, when the number of new edges is small.