On the Mapping Problem
- 1 March 1981
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-30 (3) , 207-214
- https://doi.org/10.1109/tc.1981.1675756
Abstract
In array processors it is important to map problem modules onto processors such that modules that communicate with each other lie, as far as possible, on adjacent processors. This mapping problem is formulated in graph theoretic terms and shown to be equivalent, in its most general form, to the graph isomorphism problem. The problem is also very similar to the bandwidth reduction problem for sparse matrices and to the quadratic assignment problem.Keywords
This publication has 7 references indexed in Scilit:
- A Linear Time Algorithm for Deciding Interval Graph IsomorphismJournal of the ACM, 1979
- Probabilistic analysis of a canonical numbering algorithm for graphsProceedings of Symposia in Pure Mathematics, 1979
- The graph isomorphism diseaseJournal of Graph Theory, 1977
- An Algorithm for Reducing the Bandwidth and Profile of a Sparse MatrixSIAM Journal on Numerical Analysis, 1976
- GRAPH THEORY AND GAUSSIAN ELIMINATIONPublished by Elsevier ,1976
- A Review of the Placement and Quadratic Assignment ProblemsSIAM Review, 1972
- Several Strategies for Reducing the Bandwidth of MatricesPublished by Springer Nature ,1972