Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420254 | Discrete Applied Mathematics | 2011 | 16 Pages |
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 numbers. 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
David Coudert, Jean-Sébastien Sereni,