The complexity of finding uniform emulations on fixed graphs
type: Item
instance of: scholarly article
title: The complexity of finding uniform emulations on fixed graphs
zbMATH Open document ID: 0656.68045
DOI: 10.1016/0020-0190(88)90051-8
author: Hans L. Bodlaender
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://dspace.library.uu.nl/handle/1874/16278
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4072378
zbMATH Keywords: parallel computing
zbMATH Keywords: simulations of networks
zbMATH Keywords: Uniform emulations
zbMATH Keywords: NP- complete
MaRDI profile type: Publication
OpenAlex ID: W2126696635
Wikidata QID: Q59568115
cites work: Simulation of large networks on smaller networks
cites work: Q3681950
cites work: Quotient Networks
cites work: Q4198056
DBLP publication ID: journals/ipl/Bodlaender88a
description: scientific article; zbMATH DE number 4072378