The complexity of finding uniform emulations on fixed graphs

H.L. Bodlaender

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)137-141
Number of pages5
JournalInformation Processing Letters
Volume29
Issue number3
DOIs
Publication statusPublished - 26 Oct 1988
Externally publishedYes

Keywords

  • Emulation
  • NP-completeness
  • parallel computing

Fingerprint

Dive into the research topics of 'The complexity of finding uniform emulations on fixed graphs'. Together they form a unique fingerprint.

Cite this