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.
- 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