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].
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2009, 109 (10), pp.463-467. 〈http://dx.doi.org/10.1016/j.ipl.2009.01.003〉. 〈10.1016/j.ipl.2009.01.003〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00399669
Contributeur : Serge Gaspers <>
Soumis le : dimanche 28 juin 2009 - 01:42:22
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

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. 〈http://dx.doi.org/10.1016/j.ipl.2009.01.003〉. 〈10.1016/j.ipl.2009.01.003〉. 〈lirmm-00399669〉

Partager

Métriques

Consultations de la notice

359