Technical Report 209-1989

Title

An Efficient Parallel Logarithmic Time Algorithm for the Channel Routing Problem

Authors

Dorothea Wagner and Frank Wagner

Publication

DISAM, vol. 40, 1992, pp. 73-81

extended abstract in Methods of Operations Research 60 (1989) pp. 263-266

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

In this paper we present a parallel algorithm for the channel routing problem, using the knock-knee mode. The algorithm requires O(log n) time with O(n²/log n) processors on a CREW-PRAM. The wire layout constructed by this algorithm is area-optimal if the channel routing problem is a permutation channel routing problem. For the general channel routing problem it determines a wire layout, which uses a minimal number of vertical lines and only a small number of additional horizontal lines.