The complexity of finding uniform emulations on fixed graphs

DOI10.1016/0020-0190(88)90051-8MaRDI QIDQ1110329zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hans L. Bodlaender

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/16278

zbMATH Keywords

NP- completeparallel computingsimulations of networksUniform emulations

Mathematics Subject Classification ID

Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• The complexity of finding uniform emulations on paths and ring networks
• Uniform d‐emulations of rings, with an application to distributed virtual ring construction
• Uniform homomorphisms of de Bruijn and Kautz networks
• Uniform emulations of Cartesian-product and Cayley graphs
• scientific article; zbMATH DE number 3903985

Cites work

• scientific article; zbMATH DE number 3903985 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Quotient Networks
• Simulation of large networks on smaller networks

Cited in

(6)

• On tree-partition-width
• Uniform d‐emulations of rings, with an application to distributed virtual ring construction
• Tree-partitions with bounded degree trees
• Product structure of graph classes with bounded treewidth
• Product structure of graph classes with strongly sublinear separators
• The complexity of finding uniform emulations on paths and ring networks

This page was built for publication: The complexity of finding uniform emulations on fixed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1110329)