Skip to Main content Skip to Navigation
Journal articles

Clean the Graph Before You Draw It!

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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00399669
Contributor : Serge Gaspers <>
Submitted on : Sunday, June 28, 2009 - 1:42:22 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

534