Abstract
This paper introduces a graph model, conflict graph, to represent the conflict resolution problem in multistage interconnection networks. This model shows that the conflict resolution problem is NP-complete, since it is equivalent to node coloring problem in conflict graph. Three heuristic polynomial algorithms for conflict resolution are presented.
Original language | English (US) |
---|---|
Title of host publication | Unknown Host Publication Title |
Publisher | ACM |
Pages | 422 |
Number of pages | 1 |
ISBN (Print) | 0897911504 |
State | Published - 1985 |
Externally published | Yes |
ASJC Scopus subject areas
- General Engineering