| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427791 | Information Processing Letters | 2009 | 5 Pages |
Abstract
We prove a relationship between the Cleaning problem and the Balanced Vertex-Ordering problem, namely that the minimum total imbalance of a graph equals twice the brush number of a graph. This equality has consequences for both problems. On one hand, it allows us to prove the NP-completeness of the Cleaning problem, which was conjectured by Messinger et al. [M.-E. Messinger, R.J. Nowakowski, P. Prałat, Cleaning a network with brushes, Theoret. Comput. Sci. 399 (2008) 191–205]. On the other hand, it also enables us to design a faster algorithm for the Balanced Vertex-Ordering problem [J. Kára, K. Kratochvíl, D. Wood, On the complexity of the balanced vertex ordering problem, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 193–202].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
