Exhibition Program

In a road or telecommunication network, an edge (link) may be congested and may incur more cost if many people use it. We can compute how much each edge will be congested if each user of such network chooses a path (route) selfishly, i.e. chooses a path with minimum cost without any guidance or control. The computation of congestion requires calculation of probability for each of all available paths, which is generally prohibitive because there are a great many number of paths. To overcome this problem, we use a data structure called binary decision diagram to represent all available paths compactly. With this data structure, we can speed up the computation dramatically, and can compute such state of a network with realistic size. This study enables us to predict the state of congestion for a road and telecommunication network in a simple way, which is useful for designing such networks.