Abstract
In this paper, we present an ()(l) time algorithm to solve the minimum coloring problem defined on a set of intervals, which is also called the channel assignment problem. This problem has not been solved in O(1) time before, even on the idealistic CRCW PRAM model. For large-sized problems, it is desirable to have fast hardware solutions. Our algorithm is based on the processor arrays with a reconfigurable bus system (abbreviated to PARBS) that consists of a processor array and a reconfigurable bus system. In order to solve this problem with constant time complexity, we first transform the “left-edge” channel assignment algorithm to the parenthesis-matching problem. Based on this novel scheme, we are able to explore constant-time parallel algorithms to solve the minimum coloring problem for n intervals, which is also called the channel assignment problem, on a PARBS with ()(n2) processors.
| Original language | English |
|---|---|
| Pages (from-to) | 884-890 |
| Number of pages | 7 |
| Journal | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
| Volume | 13 |
| Issue number | 7 |
| DOIs | |
| Publication status | Published - 1994 Jul |
Keywords
- Complexity
- channel assignment problem
- computation model
- minimum-coloring problem
- parallel processing
- processor array
- reconfigurable bus system
ASJC Scopus subject areas
- Software
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering