Abstract
Uniform emulations are a method to obtain efficient and structure-preserving simulations of large networks on smaller networks. We show that for every fixed graph H, which is connected (or strongly connected in the case of directed graphs) but not complete, the problem to decide whether another (strongly) connected graph G can be uniformly emulated on H is NP-complete.
Original language | English |
---|---|
Pages (from-to) | 137-141 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 29 |
Issue number | 3 |
DOIs | |
Publication status | Published - 26 Oct 1988 |
Externally published | Yes |
Keywords
- Emulation
- NP-completeness
- parallel computing