The complexity of finding uniform emulations on fixed graphs

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer 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-2Engels
Pagina's (van-tot)137-141
Aantal pagina's5
TijdschriftInformation Processing Letters
Volume29
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 26 okt 1988
Extern gepubliceerdJa

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

Citeer dit