Article ID Journal Published Year Pages File Type
420254 Discrete Applied Mathematics 2011 16 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,