کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420254 | 683913 | 2011 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Characterization of graphs and digraphs with small process numbers
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 11, 6 July 2011, Pages 1094–1109
Journal: Discrete Applied Mathematics - Volume 159, Issue 11, 6 July 2011, Pages 1094–1109
نویسندگان
David Coudert, Jean-Sébastien Sereni,