Network Planning
Data Structures Assignment
NTHU EE and CS
Overview
• Given a graph
• Each node stands for a building
• Node 0 stands for a video source (e.g., a Netflix server)
• Each edge stands for a possible connection
• Each edge is specified by its latency and bandwidth
• Task
• We wants the network to be a spanning tree
• Find the minimum-possible latency from the video
source to each building
• Find the maximum-possible bandwidth from the video
source to each building
Example
(latency, bandwidth)
(1, 3)
(1, 4) (1, 3)
(5, 5)
(1, 3)
(4, 2)
(4, 2)
(3, 6)
(3, 3)
0
1
2
3
4
6
5
Video
source
7
(1, 9)
Min-Latency Plan
(1, 3)
(1, 4) (1, 3)
(5, 5)
(1, 3)
(4, 2)
(4, 2)
(3, 6)
(3, 3)
0
1
2
3
4
6
5
1
2
3
4
7
3
Latency is
additive
along a path
7
(1, 9)
inf
Video
source
Max-Bandwidth Plan
(1, 3)
(1, 4) (1, 3)
(5, 5)
(1, 3)
(4, 2)
(4, 2)
(3, 6)
(3, 3)
0
1
2
3
4
6
5
6
5
3
3
3
3
Bandwidth is
the bottleneck
along a path
7
(1, 9)
0
Video
source
Input
8
10
7 5 1 9
0 1 1 3
1 5 1 4
5 6 1 3
6 2 1 3
0 2 5 5
0 4 3 6
2 6 4 2
4 6 4 2
2 3 3 3
# of buildings (<1000)
e.g., 8 means buildings 0~7
# of candidate connections
candidate connections
e.g., "7 5 1 9" denotes:
7 5
latency = 1
bandwidth = 9
latency is an integer between 1~10
bandwidth is an integer between 1~30
Output
1 1 3
2 4 5
3 7 3
4 3 6
5 2 3
6 3 3
7 inf 0
Buildings
(1, 2, …)
Min latency
Max bandwidth
• Unconnected building
• Latency = "inf"
• Bandwidth = 0
