Thumbnail
Access Restriction
Subscribed

Author Harada, Kazuaki
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Permutation ♦ Combinatorial algebra ♦ Graph theory ♦ Scheduling
Abstract Systematic generation of a specific class of permutations fundamental to scheduling problems is described.In a nonoriented complete graph with n vertices, Hamiltonian circuits equivalent to 1/2(n - 1)! specific permutations of n elements, termed rosary permutations, can be defined. Each of them corresponds to two circular permutations which mirror-image each other, and is generated successively by a number system covering 3·4· ··· ·(n - 1) sets of edges. Every set of edges {ek}, 1 ≤ ek ≤ k, 3 ≤ k ≤ n - 1 is determined recursively by constructing a Hamiltonian circuit with k vertices from a Hamiltonian circuit with k - 1 vertices, starting with the Hamiltonian circuit of 3 vertices. The basic operation consists of transposition of a pair of adjacent vertices where the position of the pair in the permutation is determined by {ek}. Two algorithms treating the same example for five vertices are presented.It is very easy to derive all possible n! permutations from the 1/2(n - 1)! rosary permutations by cycling the permutations and by taking them in the reverse order—procedures which can be performed fairly efficiently by computer.
Description Affiliation: Washington Univ., St. Louis, MI (Harada, Kazuaki)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 14
Issue Number 6
Page Count 7
Starting Page 373
Ending Page 379


Open content in new tab

   Open content in new tab
Source: ACM Digital Library