Characterization of graphs and digraphs with small process number

Abstract : We introduce the process number of a digraph as a tool to study rerouting issues in \wdm networks. This parameter is closely related to the vertex separation (or pathwidth). We consider the recognition and the characterization of (di)graphs with small process number. In particular, we give a linear time algorithm to recognize (and process) graphs with process number at most 2, along with a characterization in terms of forbidden minors, and a structural description. As for digraphs with process number 2, we exhibit a characterization that allows one to recognize (and process) them in polynomial time.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2011, 159 (11), pp.1094-1109. <10.1016/j.dam.2011.03.010>
Liste complète des métadonnées


https://hal.inria.fr/inria-00587717
Contributeur : David Coudert <>
Soumis le : jeudi 21 avril 2011 - 12:23:24
Dernière modification le : mercredi 12 octobre 2016 - 01:23:15
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 00:25:58

Fichier

dam-noformat.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Jean-Sébastien Sereni. Characterization of graphs and digraphs with small process number. Discrete Applied Mathematics, Elsevier, 2011, 159 (11), pp.1094-1109. <10.1016/j.dam.2011.03.010>. <inria-00587717>

Partager

Métriques

Consultations de
la notice

279

Téléchargements du document

101