Clean the graph before you draw it!
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 A(P-completeness of the CLEANING problem, which was conjectured by Messinger et al. [M.-E. Messinger, R.J. Nowakowski, P. Pralat, 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. Kara, K. Kratochvil, D. Wood, On the complexity of the balanced vertex ordering problem, Discrete Math. Theor. Comput. Sci. 9 (1) (2007) 193-202]. (C) 2009 Elsevier B.V. All rights reserved.
balanced vertex-ordering brush number graph algorithms computational complexity