COORDTNATTNG l'ET3131,E MOTION ON GIlAPIIS, THE I)JAMETEH. OF I'EItMUTATION CROUPS, AND APPLICATIONS
Daniel Kornhauser, Gary Lee Miller, Paul G. Spirakis · 1984
We consider the following generalization of the familiar '15-puzzle' which arises from issues in niemory manngrment, in distributed systems: Idet G be a. papti with n vertices with k < n pebblrs nriniberet! 1 j...,k oil distinct vrrticcs. A move coiisia~s OF transf':':.rririg a pei'hlc to an adjr~c(~iit iinoccripicd vertex. Is one arraiigcnierit of th(= pebblcs re;diable lkrm another?. We present c 1'-time decision algorithm, and provr inatching O(n) upper and lower !,ounds on the numbei of Inovrs required. These resalts extend thosc of Wilson ;1974), who considered G biconnrctcd and k=n- I, with no analysis of number of moves. We nlbo consider the rlucsf ion of permutation group diameter. Driscoli and Ihrst (1983) ohtairic4 a polyno- inial upper bound on thc diameter of groups grnrrnt,rd by bounded lrrigth cyclrs. We have tlie following ~ubex- ponential bound for (crLain uriboondcd cy~les. 11' G'