The complexity of finding uniform emulations on fixed graphs (Q1110329): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q59568115, #quickstatements; #temporary_batch_1711196317277 |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Simulation of large networks on smaller networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3681950 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Quotient Networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank |
Latest revision as of 19:24, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The complexity of finding uniform emulations on fixed graphs |
scientific article |
Statements
The complexity of finding uniform emulations on fixed graphs (English)
0 references
1988
0 references
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.
0 references
parallel computing
0 references
simulations of networks
0 references
Uniform emulations
0 references
NP- complete
0 references