Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Thursday, April 21, 2011 - 12:23:24 PM
Last modification on : Thursday, January 20, 2022 - 5:32:16 PM
Long-term archiving on: : Sunday, December 4, 2016 - 12:25:58 AM


Files produced by the author(s)



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⟩



Les métriques sont temporairement indisponibles