×
Annexstein, Fred S.; Kuchko, Eugene A.

A ranking algorithm for Hamilton paths in shuffle-exchange graphs. (English) Zbl 1502.68199

Akl, Selim G. (ed.) et al., Algorithms and data structures. 4th international workshop, WADS ’95, Kingston, Canada, August 16–18, 1995. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 955, 263-269 (1995).
Summary: In previous work, R. Feldmann and P. Mysliwietz [Lect. Notes Comput. Sci. 629, 246–254 (1992; Zbl 1494.68193)] showed that every shuffle-exchange graph contains a Hamilton path. In this paper, we show that there is a linear time ranking algorithm associated with that Hamilton path. The ranking algorithm returns the rank-position of each node of the graph with respect to the order given by the Hamilton path. Ranking algorithms are important for they can be applied to yield efficient implementations of certain network emulations using SIMD-style parallel algorithms for translating node labels.
For the entire collection see [Zbl 0847.00049].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C45 Eulerian and Hamiltonian graphs
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 1494.68193
PDF BibTeX XML Cite
\textit{F. S. Annexstein} and \textit{E. A. Kuchko}, Lect. Notes Comput. Sci. 955, 263--269 (1995; Zbl 1502.68199)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] F.S. Annexstein (1994): Ranking algorithms for hamiltonian paths in hypercubic networks, to appeal in AMS DIMACS series, Proceedings of the DIMACS Workshop on Interconnection Networks and Mapping and Scheduling Parallel Computations.
[2] F.S. Annexstein (1993): Parallel implementations of graph embeddings, in Parallel Architectures and Their Efficient Use, Lecture Notes in Computer Science 678, Springer Verlag, 207-217.
[3] R. Feldmann and P. Mysliwietz (1992): The shuffle exchange network has a Hamiltonian path, Proceedings of 17th Mathematical Foundations of Computer Science (MFCS ’92), Lecture Notes in Computer Science 629, Springer Verlag, 246-254. · Zbl 1494.68193
[4] R. Feldmann and W. Unger (1992): The cube-connected cycles network is a subgraph of the butterfly network. Parallel Processing Letters (2), 1, 13-19.
[5] D.M. Gordon (1991): Parallel sorting on Cayley graphs. \( Algorithmica (6), 554-564\). · Zbl 0729.68025
[6] F. Gray (1953): Pulse code communication, U.S. Patent Number 2,632,058.
[7] H.S. Wilf (1989): Combinatorial algorithms: an update, CBMS-55, SIAM.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.