Clean the Graph Before You Draw It! - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Information Processing Letters Year : 2009

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].

Dates and versions

lirmm-00399669 , version 1 (28-06-2009)

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More