This thesis considers a problem of finding the quickest path set for data transmission on telecommunication networks, which is a routing path set requiring the minimum time for transmitting a given amount of data units from the source to the sink. It is assumed in the problem that the data can be partitioned into smaller parts. Some solution properties are characterized, and then used to exploit a branching algorithm for the optimal solution. And another algorithm is also exploited easily to account for marginal variations on the given problem data treated by the branching algorithm. Heuristic approaches are investigated in addition and some computational experiences are discussed.
본 논문에서는 통신 네트웍에서 주어진 데이타의 전송시간을 최소화하는 문제에 대하여 다루고 있다. 이를 위하여 주어진 데이타는 분할되어, 선택된 경로들을 통하여 전송되는 방법이 제안되었다.
최적해가 가져야 할 몇가지 성질들을 규명하였으며, 이 성질들을 이용하여 해를 구하는 분지 기법(branching algorithm)이 제시되었고, 전송되는 데이타 양에 작은 변동이 있는 경우의 최적해를 구하는 기법이 또한 제시되었다. 계산의 효율성을 위하여 근사해를 구하는 발견적 기법이 두 가지 제시되었다. 성능평가를 통하여 제시된 발견적 기법들이 우수한 근사해를 구해 냄을 알 수 있었다.
