×

Sorting on graphs by adjacent swaps using permutation groups. (English) Zbl 1398.68116

Summary: This paper is a review of sorting on several well-known graphs by adjacent swaps using permutation groups. Given a graph with a line, star, complete, or ring topology having \(n\) vertices (numbered from 1 to \(n\)), we place \(n\) objects (numbered from 1 to \(n\)) arbitrarily in such a way that exactly one object is placed on each vertex. A sorting procedure is intended to reach the target object placement in which each object \(i\) is placed on vertex \(i\) for \(1 \leq i \leq n\). Now, the problem is to find a minimum-length sequence of adjacent swaps needed to sort the initial arrangement of \(n\) objects on \(n\) vertices in the graph, which employs a known permutation sorting or permutation decomposition procedure using a generating set of a symmetric group \(\mathfrak{S}_n\). This paper reviews the existing permutation sorting and permutation decomposition procedures for sorting on graphs with line, star, complete, and ring topologies by adjacent swaps. We also provide concrete examples and our own implementation for this review paper in order to describe how abstract group-theoretical methods are used to find a minimum-length sequence of adjacent swaps needed to sort objects on those graphs.

MSC:

68P10 Searching and sorting
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
20B40 Computational methods (permutation groups) (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hungerford, T., Algebra (1980), Springer: Springer New York, NY · Zbl 0442.00002
[2] Diaconis, P., (Group Representations in Probability and Statistics. Group Representations in Probability and Statistics, Institute of Mathematical Statistics Lecture Notes—Monograph Series (1988), Institute of Mathematical Statistics: Institute of Mathematical Statistics Hayward, CA) · Zbl 0695.60012
[3] Heydemann, M., Cayley graphs and interconnection networks, (Hahn, G.; Sabidussi, G., Graph Symmetry: Algebraic Methods and Applications. Graph Symmetry: Algebraic Methods and Applications, NATO ASI Series, vol. 497 (1997), Springer: Springer New York, NY), 167-224 · Zbl 0885.05075
[4] Knuth, D. E., The Art of Computer Programming. Vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010
[5] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), The MIT Press: The MIT Press Cambridge, MA · Zbl 1047.68161
[6] Mehlhorn, K., (Sorting and Searching. Sorting and Searching, Eatcs Monographs on Theoretical Computer Science (1984), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ) · Zbl 0556.68001
[7] Graf, D., Scheduling and Sorting Algorithms for Robotic Warehousing Systems (2015), ETH Zürich: ETH Zürich Zürich, Switzerland, (Master’s thesis)
[8] Graf, D., How to sort by walking on a tree, (Bansal, N.; Finocchi, I., Algorithms - ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings (2015), Springer Berlin, Heidelberg: Springer Berlin, Heidelberg Berlin, Heidelberg), 643-655 · Zbl 1369.68175
[9] Lin, F.-C.; Hsu, J. Y.-J., A genetic algorithm approach for the object-sorting task problem, (IEEE International Conference on Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century, Vol. 1 (1995), IEEE: IEEE New York, NY), 241-246
[10] Yamanaka, K.; Demaine, E. D.; Ito, T.; Kawahara, J.; Kiyomi, M.; Okamoto, Y.; Saitoh, T.; Suzuki, A.; Uchizawa, K.; Uno, T., Swapping labeled tokens on graphs, Theoret. Comput. Sci., 586, 81-94 (2015) · Zbl 1327.68336
[11] Thompson, C. D.; Kung, H. T., Sorting on a mesh-connected parallel computer, (Proceedings of the Eighth Annual ACM Symposium on Theory of Computing. Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, STOC’76 (1976), ACM: ACM New York, NY), 58-64 · Zbl 0365.68035
[12] Rajasekaran, S.; Wei, D. S., Selection, routing, and sorting on the star graph, J. Parallel Distrib. Comput., 41, 2, 225-233 (1997)
[13] Heath, L. S.; Vergara, J. P.C., Sorting by bounded block-moves, Discrete Appl. Math., 88, 181-206 (1998) · Zbl 0927.68024
[14] Fertin, G.; Labarre, A.; Rusu, I.; Tannier, É.; Vialette, S., Combinatorics of Genome Rearrangements (2009), MIT Press: MIT Press Cambridge, MA · Zbl 1170.92022
[15] Christie, D. A., Genome rearrangement problems (1998), University of Glasgow: University of Glasgow Glasgow, UK, (Ph.D. thesis)
[16] Bulteau, L.; Fertin, G.; Rusu, I., Sorting by transpositions is difficult, SIAM J. Discrete Math., 26, 3, 1148-1180 (2012) · Zbl 1256.05004
[17] Yamanaka, K.; Horiyama, T.; Kirkpatrick, D.; Otachi, Y.; Saitoh, T.; Uehara, R.; Uno, Y., Swapping colored tokens on graphs, (Dehne, F.; Sack, J.-R.; Stege, U., Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings (2015), Springer International Publishing: Springer International Publishing Cham (ZG), Switzerland), 619-628 · Zbl 1451.68135
[18] Kim, D., Task swapping networks in distributed systems, Int. J. Comput. Math., 90, 2221-2243 (2013) · Zbl 1311.68027
[19] Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 555-566 (1989) · Zbl 0678.94026
[20] Lakshmivarahan, S.; Jwo, J.-S.; Dhall, S. K., Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey, Parallel Comput., 19, 4, 361-407 (1993) · Zbl 0777.05064
[21] Jerrum, M., The complexity of finding minimum-length generator sequences, Theoret. Comput. Sci., 36, 265-289 (1985) · Zbl 0564.68031
[22] Fraleigh, J. B., A First Course in Abstract Algebra (1998), Addison-Wesley: Addison-Wesley Reading, MA
[25] Zhang, H. L.; Leung, C. H.C.; Raikundalia, G. K., Classification of intelligent agent network topologies and a new topological description language for agent networks, (Shi, Z.; Shimohara, K.; Feng, D., Intelligent Information Processing III. Intelligent Information Processing III, IFIP International Federation for Information Processing, vol. 228 (2006)), 21-31
[27] Zhu, Q., Topologies of agents interactions in knowledge intensive multi-agent systems for networked information services, Adv. Eng. Inf., 20, 31-45 (2006)
[28] Pak, I., Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ARY trees, Discrete Math., 204, 329-335 (1999) · Zbl 0931.05003
[30] Irving, J.; Rattan, A., Factorizations of permutations into star transpositions, Discrete Math., 309, 1435-1442 (2009) · Zbl 1181.05004
[31] Mackiw, G., Permutations as products of transpositions, Amer. Math. Monthly, 102, 438-440 (1995) · Zbl 0831.05003
[32] Neuenschwander, D., On the representation of permutations as products of transpositions, Elem. Math., 56, 1-3 (2001) · Zbl 0984.05002
[33] Biggs, N., Algebraic Graph Theory (2013), Cambridge University Press: Cambridge University Press Cambridge, MA
[34] Babai, L., Spectra of Cayley graphs, J. Combin. Theory Ser. B, 27, 2, 180-189 (1979) · Zbl 0338.05110
[35] Meier, J., Groups, Graphs and Trees: An Introduction to the Geometry of Infinite Groups (2008), Cambridge University Press: Cambridge University Press Cambridge, MA · Zbl 1276.20052
[36] Björner, A.; Brenti, F., Combinatorics of Coxeter Groups (2005), Springer: Springer New York, NY · Zbl 1110.05001
[37] Camelo, M.; Vilà, P.; Fàbrega, L.; Papadimitriou, D., Cayley-graph-based data centers and space requirements of a routing scheme using automata, (Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems Workshops. Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems Workshops, ICDCSW’14 (2014), IEEE Computer Society: IEEE Computer Society Washington, DC), 63-69
[38] Camelo, M.; Papadimitriou, D.; Fàbrega, L.; Vilà, P., Efficient routing in data center with underlying cayley graph, (Contucci, P.; Menezes, R.; Omicini, A.; Poncela-Casasnovas, J., Complex Networks V: Proceedings of the 5th Workshop on Complex Networks CompleNet 2014 (2014), Springer International Publishing: Springer International Publishing Cham (ZG), Switzerland), 189-197
[39] Gutjahr, W. J.; Hitz, M.; Mueck, T. A., Task assignment in Cayley interconnection topologies, Parallel Comput., 23, 10, 1429-1460 (1997) · Zbl 0894.68023
[40] Boldi, P.; Vigna, S., Minimal sense of direction and decision problems for Cayley graphs, Inform. Process. Lett., 64, 6, 299-303 (1997) · Zbl 1338.68211
[41] Kim, D.; Noel, E.; Tang, K. W., Expanded Borel Cayley graphs (Ex-BCGs): A novel communication topology for multi-agent systems, J. Netw. Comput. Appl., 37, 47-61 (2014)
[42] Schiavinotto, T.; Stützle, T., A review of metrics on permutations for search landscape analysis, Comput. Oper. Res., 34, 10, 3143-3153 (2007) · Zbl 1185.90115
[43] Cheng, E.; Lipták, L.; Shawash, N., Orienting Cayley graphs generated by transposition trees, Comput. Math. Appl., 55, 11, 2662-2672 (2008) · Zbl 1142.05327
[44] Kaneko, K.; Suzuki, Y., Node-to-node internally disjoint paths problem in bubble-sort graphs, (10th IEEE Pacific Rim International Symposium on Dependable Computing, 2004. Proceedings (2004), IEEE: IEEE New York, NY), 173-182
[46] Suzuki, Y.; Kaneko, K.; Nakamori, M., Node-disjoint paths algorithm in a transposition graph, IEICE Trans. Inf. Syst., E89-D, 10, 2600-2605 (2006)
[47] Dietzfelbinger, M.; Madhavapeddy, S.; Sudborough, I. H., Three disjoint path paradigms in star networks, (Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on, Dec 2-5 (1991), IEEE: IEEE New York, NY), 400-406
[48] Lai, C.-N., On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups, Theoret. Comput. Sci., 571, 10-20 (2015) · Zbl 1306.05115
[49] Lai, C. N., Optimal construction of all shortest node-disjoint paths in hypercubes with applications, IEEE Trans. Parallel Distrib. Syst., 23, 6, 1129-1134 (2012)
[50] Kaneko, K.; Sawada, N., An algorithm for node-to-node disjoint paths problem in burnt pancake graphs, IEICE Trans. Inf. Syst., E90-D, 1, 306-313 (2007)
[51] Snyder, M.; Gerstein, M., Defining genes in the genomics era, Science, 300, 5617, 258-260 (2003)
[52] Jones, N. C.; Pevzner, P., An Introduction to Bioinformatics Algorithms (2004), MIT Press: MIT Press Cambridge, MA
[53] Elias, I.; Hartman, T., A 1.375-approximation algorithm for sorting by transpositions, IEEE/ACM Trans. Comput. Biol. Bioinform., 3, 4, 369-379 (2006)
[54] Feng, J.; Zhu, D., Faster algorithms for sorting by transpositions and sorting by block interchanges, ACM Trans. Algorithms, 3, 3 (2007), Article No. 25 · Zbl 1192.68194
[55] Bafna, V.; Pevzner, P. A., Genome rearrangements and sorting by reversals, SIAM J. Comput., 25, 2, 272-289 (1996) · Zbl 0844.68123
[56] Braga, M. D.; Sagot, M.-F.; Scornavacca, C.; Tannier, E., Exploring the solution space of sorting by reversals, with experiments and an application to evolution, IEEE/ACM Trans. Comput. Biol. Bioinform., 5, 3, 348-356 (2008)
[57] Badr, G.; Swenson, K. M.; Sankoff, D., Listing all parsimonious reversal sequences: New algorithms and perspectives, (Proceedings of the 2010 International Conference on Comparative Genomics. Proceedings of the 2010 International Conference on Comparative Genomics, RECOMB-CG’10 (2010), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 39-49
[58] Lin, Y. C.; Lu, C. L.; Chang, H.-Y.; Tang, C. Y., An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species, J. Comput. Biol., 12, 102-112 (2005)
[59] Chin, L. L.; Ying, C. L.; Yen, L. H.; Chuan, Y. T., Analysis of genome rearrangement by block-interchanges, (Comparative Genomics (2007), Humana Press: Humana Press Totowa, NJ), 121-134, (Chapter)
[60] Clair, C. St.; Visick, J. E., Exploring Bioinformatics: A Project-Based Approach (2013), Jones and Bartlett Publishers, Inc.: Jones and Bartlett Publishers, Inc. Sudbury, MA
[61] Solomon, A.; Sutcliffe, P.; Lister, R., Sorting circular permutations by reversal, (Dehne, F.; Sack, J.-R.; Smid, M., Algorithms and Data Structures: 8th International Workshop, WADS 2003, Ottawa, Ontario, Canada, July 30-August 1, 2003. Proceedings (2003), Springer Berlin, Heidelberg: Springer Berlin, Heidelberg Berlin, Heidelberg), 319-328 · Zbl 1278.68227
[62] Feng, X.; Chitturi, B.; Sudborough, H., Sorting circular permutations by bounded transpositions, (Arabnia, H. R., Advances in Computational Biology. Advances in Computational Biology, Advances in Experimental Medicine and Biology, vol. 680 (2010), Springer: Springer New York, NY), 725-736
[63] Chitturi, B.; Sudborough, H.; Voit, W.; Feng, X., Adjacent swaps on strings, (Proceedings of the 14th Annual International Conference on Computing and Combinatorics. Proceedings of the 14th Annual International Conference on Computing and Combinatorics, COCOON’08 (2008), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 299-308 · Zbl 1148.68415
[64] Pevzner, P. A., Computational Molecular Biology: An Algorithmic Approach (2000), MIT Press: MIT Press Cambridge, MA · Zbl 0972.92011
[65] Bafna, V.; Beaver, D.; Fürer, M.; Pevzner, P. A., Circular permutations and genome shuffling, (Sankoff, D.; Nadeau, J. H., Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families (2000), Springer Netherlands: Springer Netherlands Dordrecht, Netherlands), 199-206 · Zbl 1137.92334
[66] Egri-Nagy, A.; Gebhardt, V.; Tanaka, M. M.; Francis, A. R., Group-theoretic models of the inversion process in bacterial genomes, J. Math. Biol., 69, 1, 243-265 (2014) · Zbl 1293.92015
[67] Labarre, A., Edit distances and factorisations of even permutations, (Proceedings of the 16th Annual European Symposium on Algorithms. Proceedings of the 16th Annual European Symposium on Algorithms, ESA’08 (2008), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 635-646 · Zbl 1158.68370
[68] Labarre, A., Lower bounding edit distances between permutations, SIAM J. Discrete Math., 27, 3, 1410-1428 (2013) · Zbl 1286.68366
[69] Akers, S. B.; Harel, D.; Krishnamurthy, B., The star graph: An attractive alternative to the n-cube, (Scherson, I. D.; Youssef, A. S., Interconnection Networks for High-performance Parallel Computers (1994), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 145-152
[71] Barg, A.; Mazumdar, A., Codes in permutations and error correction for rank modulation, IEEE Trans. Inform. Theory, 56, 7, 3158-3165 (2010) · Zbl 1366.94657
[72] Portier, F. J.; Vaughan, T. P., Whitney numbers of the second kind for the star poset, European J. Combin., 11, 3, 277-288 (1990) · Zbl 0706.06006
[73] Qiu, K.; Akl, S. G., On some properties of the star graph, VLSI Des., 2, 4, 389-396 (1995)
[74] Grusea, S.; Labarre, A., Asymptotic normality and combinatorial aspects of the prefix exchange distance distribution, Adv. in Appl. Math., 78, 94-113 (2016) · Zbl 1358.05008
[75] Arndt, J., Matters Computational: Ideas, Algorithms, Source Code (2010), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. New York, NY · Zbl 1210.68128
[76] Williamson, D. P.; Shmoys, D. B., The Design of Approximation Algorithms (2011), Cambridge University Press: Cambridge University Press New York, NY · Zbl 1219.90004
[77] Ganesan, A., An efficient algorithm for the diameter of Cayley graphs generated by transposition trees, IAENG Int. J. Appl. Math., 42, 4, 214-223 (2012) · Zbl 1512.05372
[78] Cai, L.; Corneil, D. G., Tree spanners, SIAM J. Discrete Math., 8, 3, 359-387 (1995) · Zbl 0832.05037
[79] Heath, L. S.; Vergara, J. C., Sorting by short swaps, J. Comput. Biol., 10, 775-789 (2003)
[80] Caprara, A., The reversal median problem, INFORMS J. Comput., 15, 1, 93-113 (2003) · Zbl 1238.90099
[81] Hannenhalli, S.; Pevzner, P. A., Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals, J. ACM, 46, 1, 1-27 (1999) · Zbl 1064.92510
[82] Konstantinova, E., On some structural properties of star and pancake graphs, (Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede (2013), Springer Berlin, Heidelberg: Springer Berlin, Heidelberg Berlin, Heidelberg), 472-487, (Chapter) · Zbl 1377.05159
[83] Gates, W. H.; Papadimitriou, C. H., Bounds for sorting by prefix reversal, Discrete Math., 27, 1, 47-57 (1979) · Zbl 0397.68062
[84] Christie, D. A., Sorting permutations by block-interchanges, Inform. Process. Lett., 60, 4, 165-169 (1996) · Zbl 0900.68232
[85] Ajana, Y.; Jean-François, L.; Tillier, E. R.; El-Mabrouk, N., Exploring the set of all minimal sequences of reversals-an application to test the replication-directed reversal hypothesis, (Guigó, R.; Gusfield, D., Algorithms in Bioinformatics: Second International Workshop, WABI 2002 Rome, Italy, September 17-21, 2002 Proceedings (2002), Springer Berlin, Heidelberg: Springer Berlin, Heidelberg Berlin, Heidelberg), 300-315 · Zbl 1016.68690
[86] Amritanjali; Sahoo, G., Listing sorting sequences of reversals and translocations, (Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, BCB’13 (2013), ACM: ACM New York, NY), 712
[87] Ouangraoua, A.; Bergeron, A., Combinatorial structure of genome rearrangements scenarios, J. Comput. Biol., 17, 1129-1144 (2010)
[88] Siepel, A. C., An algorithm to enumerate all sorting reversals, (Proceedings of the Sixth Annual International Conference on Computational Biology. Proceedings of the Sixth Annual International Conference on Computational Biology, RECOMB’02 (2002), ACM: ACM New York, NY), 281-290
[89] Miklós, I.; Darling, A., Efficient sampling of parsimonious inversion histories with application to genome rearrangement in Yersinia, Genome. Biol. Evol., 1, 1, 153-164 (2009)
[90] Miklós, I.; Smith, H., Sampling and counting genome rearrangement scenarios, BMC Bioinformatics, 16, 14, 1-14 (2015)
[91] Stanley, R. P., On the number of reduced decompositions of elements of coxeter groups, European J. Combin., 5, 4, 359-372 (1984) · Zbl 0587.20002
[92] Eriksson, H., Computational and combinatorial aspects of Coxeter groups (1994), KTH Royal Institute of Technology: KTH Royal Institute of Technology Stockholm, Sweden, (Ph.D. thesis)
[93] Tenner, B. E., A combinatorial proof of symmetry among minimal star factorizations, Discrete Math., 312, 16, 2482-2490 (2012) · Zbl 1246.05006
[94] Hurwitz, A., Ueber Riemann’sche Flächen mit gegebenen Verzweigungspunkten, Math. Ann., 39, 1, 1-60 (1891) · JFM 23.0429.01
[95] Bousquet-Mélou, M.; Schaeffer, G., Enumeration of planar constellations, Adv. in Appl. Math., 24, 4, 337-368 (2000) · Zbl 0955.05004
[97] Bosma, W.; Cannon, J.; Playoust, C., The magma algebra system I: The user language, J. Symbolic Comput., 24, 3, 235-265 (1997) · Zbl 0898.68039
[100] Racine, J., The Cygwin tools: a GNU toolkit for windows, J. Appl. Econometrics, 15, 3, 331-341 (2000)
[102] Blischak, J. D.; Davenport, E. R.; Wilson, G., A quick introduction to version control with git and github, PLoS Comput. Biol., 12, 1, e1004668 (2016)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.