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

parallel computingNP- completesimulations of networksUniform emulations

Mathematics Subject Classification ID

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

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

(4)

• Product structure of graph classes with bounded treewidth
• On tree-partition-width
• Tree-partitions with bounded degree trees
• 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)