Back to Search Start Over

Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph.

Graph Partitioning and Traffic Grooming with Bounded Degree Request Graph.

Authors :
Li, Zhentao
Sau, Ignasi
Source :
Graph-theoretic Concepts in Computer Science (9783642114083); 2010, p250-261, 12p
Publication Year :
2010

Abstract

We study a graph partitioning problem which arises from traffic grooming in optical networks. We wish to minimize the equipment cost in a SONET WDM ring network by minimizing the number of Add-Drop Multiplexers (ADMs) used. We consider the version introduced by Muñoz and Sau [12] where the ring is unidirectional with a grooming factor C, and we must design the network (namely, place the ADMs at the nodes) so that it can support any request graph with maximum degree at most ∆. This problem is essentially equivalent to finding the least integer M(C,∆) such that the edges of any graph with maximum degree at most ∆ can be partitioned into subgraphs with at most C edges and each vertex appears in at most M(C,∆) subgraphs [12]. The cases where ∆= 2 and ∆ = 3,C ≠ 4 were solved by Muñoz and Sau [12]. In this article we establish the value of M(C,∆) for many more cases, leaving open only the case where ∆ ≥ 5 is odd, ]> is between 3 and C − 1, C ≥ 4, and the request graph does not contain a perfect matching. In particular, we answer a conjecture of [12]. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISBNs :
9783642114083
Database :
Complementary Index
Journal :
Graph-theoretic Concepts in Computer Science (9783642114083)
Publication Type :
Book
Accession number :
76743550
Full Text :
https://doi.org/10.1007/978-3-642-11409-0_22