Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874273 | Information Processing Letters | 2014 | 4 Pages |
Abstract
Given a directed graph G and a threshold L(r) for each node r, the rule of deterministic threshold cascading is that a node r fails if and only if it has at least L(r) failed in-neighbors. The cascading failure minimization problem is to find at most k edges to delete, such that the number of failed nodes is minimized. We prove an n1âϵ inapproximability result for the general case and a 12nϵ inapproximability result for the special case with the maximum threshold of 1.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Lei Nie, Jingjie Liu, Haicang Zhang, Zhiwei Xu,