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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

3 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	137-141
Aantal pagina's	5
Tijdschrift	Information Processing Letters
Volume	29
Nummer van het tijdschrift	3
DOI's	https://doi.org/10.1016/0020-0190(88)90051-8
Status	Gepubliceerd - 26 okt 1988
Extern gepubliceerd	Ja

Toegang tot document

10.1016/0020-0190(88)90051-8

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

Vingerafdruk Duik in de onderzoeksthema's van 'The complexity of finding uniform emulations on fixed graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit

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

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

VL - 29

SP - 137

EP - 141

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 3

ER -