کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420722 683972 2009 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Forwarding and optical indices of a graph
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Forwarding and optical indices of a graph
چکیده انگلیسی

Motivated by wavelength-assignment problems for all-to-all traffic in optical networks, we study graph parameters related to sets of paths connecting all pairs of vertices. We consider sets of both undirected and directed paths, under minimisation criteria known as edge congestion and wavelength count; this gives rise to four parameters of a graph GG: its edge forwarding index π(G)π(G), arc forwarding index π→(G), undirected optical index w(G), and directed optical index w→(G).In the paper we address two long-standing open problems: whether the equality π→(G)=w→(G) holds for all graphs, and whether indices π(G)π(G) and w(G) are hard to compute. For the first problem, we give an example of a family of planar graphs {Gk}{Gk} such that π→(Gk)≠w→(Gk). For the second problem, we show that determining either π(G)π(G) or w(G) is NP-hard.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 2, 28 January 2009, Pages 321–329
نویسندگان
,