The complexity of finding uniform emulations on fixed graphs

H.L. Bodlaender

doi:10.1016/0020-0190(88)90051-8

The complexity of finding uniform emulations on fixed graphs

H.L. Bodlaender

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	137-141
Number of pages	5
Journal	Information Processing Letters
Volume	29
Issue number	3
DOIs	https://doi.org/10.1016/0020-0190(88)90051-8
Publication status	Published - 26 Oct 1988
Externally published	Yes

Keywords

Emulation
NP-completeness
parallel computing

Access to Document

10.1016/0020-0190(88)90051-8

http://www.mendeley.com/research/complexity-finding-uniform-emulations-fixed-graphs

Cite this

@article{cc3fe8040788409ba5581f8ff951d4e6,

title = "The complexity of finding uniform emulations on fixed graphs",

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.",

keywords = "Emulation, NP-completeness, parallel computing",

author = "H.L. Bodlaender",

year = "1988",

month = oct,

day = "26",

doi = "10.1016/0020-0190(88)90051-8",

language = "English",

volume = "29",

pages = "137--141",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - The complexity of finding uniform emulations on fixed graphs

AU - Bodlaender, H.L.

PY - 1988/10/26

Y1 - 1988/10/26

N2 - 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.

AB - 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.

KW - Emulation

KW - NP-completeness

KW - parallel computing

U2 - 10.1016/0020-0190(88)90051-8

DO - 10.1016/0020-0190(88)90051-8

M3 - Article

SN - 0020-0190

VL - 29

SP - 137

EP - 141

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

The complexity of finding uniform emulations on fixed graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this