scientific article; zbMATH DE number 19194
[For the entire collection see Zbl 0734.00014.] From the authors abstract: The problem of embedding a graph into a \(d\)- dimensional hypercube and several generalizations are addressed. These generalizations arise in scheduling nodes on a hypercube connected multiprocessor. They share the feature that they may not require mappings be isomorphisms, but there are objective functions measuring the goodness of the mapping into the cube. New congestion functions, which model information flow better than the usual criteria for good embeddings, are given. Results of using stochastic optimization in embedding problems are presented. A new general heuristic to enhance the local neighborhood structure is used. Some well known problems which have analytic solutions are considered as examples, as well as several problems which are \(NP\)- complete. In the latter a branch-and-bound procedure was used to determine an optimal embedding to use in evaluating the stochastic method.
- Cover-preserving order embeddings into Boolean lattices
- Hypersphere mapper: A nonlinear programming approach to the hybercube embedding problem
- On embedding complete graphs into hypercubes
- On Relaxed Squashed Embedding of Graphs into a Hypercube
- Embedding of Grids into Optimal Hypercubes
- The complexity of congestion-1 embedding in a hypercube
- A neural optimizer for hypercube embedding
- Hypercube embedding heuristics: An evaluation
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976624)
