NSE-8G™ Standard Product Data Sheet
Preliminary
Figure 31 Example Problem
A
B
C
D
E
F
Timeslot 1
Timeslot 2
Timeslot 3
1
2
3
4
5
6
F
A
B
C
D
E
1
2
3
4
5
6
F
A
B
C
D
E
1
2
3
4
5
6
Input node F is available on timeslot 3 and output node 6 is available on timeslot 2. Merging
these two timeslots and adding the edge (F→6) results in the graph shown in Figure 31. In this
graph, the edges assigned to timeslot 3 are shown as dotted lines. The edge (F→6) is shown in
bold.
Figure 32 Merged Graph
A
B
C
D
E
F
1
2
3
4
5
6
There are 3 maximal length paths in the merged graph, (A→2→B→1), (D→5), and
(C→4→F→6→E→3). The last path mentioned requires re-labeling. If we start with edge (C→4)
and traverse the path, alternately labeling with timeslot 2 and 3, we get the graph in Figure 32.
The timeslot labeling in this graph replaces timeslots 2 and 3 in the original graph (and schedule).
Proprietary and Confidential to PMC-Sierra, Inc., and for its Customers’ Internal Use
Document ID: PMC-2010850, Issue 1
161
PMC [ PMC-SIERRA, INC ]
