Skip to Main content Skip to Navigation
Journal articles

Clean the Graph Before You Draw It!

Serge Gaspers 1 Margaret-Ellen Messinger 2 Richard J. Nowakowski 2 Pawel Pralat 2 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 View 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].
Complete list of metadata
Contributor : Serge Gaspers Connect in order to contact the contributor
Submitted on : Sunday, June 28, 2009 - 1:42:22 AM
Last modification on : Tuesday, September 6, 2022 - 4:53:29 PM

Links full text




Serge Gaspers, Margaret-Ellen Messinger, Richard J. Nowakowski, Pawel Pralat. Clean the Graph Before You Draw It!. Information Processing Letters, Elsevier, 2009, 109 (10), pp.463-467. ⟨10.1016/j.ipl.2009.01.003⟩. ⟨lirmm-00399669⟩



Record views