Premium
Minimum width 2‐layer layout of a multichanneled system
Author(s) -
Cutler M.,
Riesel Z.
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120208
Subject(s) - combinatorics , algorithm , mathematics , upper and lower bounds , time complexity , computer science , discrete mathematics , mathematical analysis
A special layout problem is considered. It is shown that the problem is NP‐complete. For a system with a small number of channels k , a polynomial algorithm is given, finding a layout with a width differing from the minimum by at most k + 1. For a system with a large number of channels k , an approximation algorithm is presented. Given an ϵ > 0 this algorithm finds a layout with a width differing from the minimum by at most ϵ Z + k + 1, where Z is a lower bound on the width. The complexity of this algorithm depends on ϵ.