| Issue |
RAIRO-Oper. Res.
Volume 58, Number 1, January-February 2024
Graphs, Combinatorics, Algorithms and Optimization
|
|
|---|---|---|
| Page(s) | 441 - 455 | |
| DOI | https://doi.org/10.1051/ro/2023134 | |
| Published online | 19 February 2024 | |
- A.V. Aho, J.E. Hopcroft and J.D. Ullman, On finding lowest common ancestors in trees, in Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC’73. Association for Computing Machinery. New York, NY, USA (1973) 253–265. [Google Scholar]
- O. Aichholzer, E.D. Demaine, M. Korman, A. Lubiw, J. Lynch, Z. Masárová, M. Rudoy, V. Vassilevska Williams and N. Wein, Hardness of Token Swapping on Trees, in 30th Annual European Symposium on Algorithms (ESA 2022). Vol. 244 of Leibniz International Proceedings in Informatics (LIPIcs), edited by S. Chechik, G. Navarro, E. Rotenberg and G. Herman. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2022) 3:1–3:15. [Google Scholar]
- S. Alstrup, C. Gavoille, H. Kaplan and T. Rauhe, Nearest common ancestors: a survey and a new algorithm for a distributed environment. Theory Comput. Syst. 37 (2004) 441–456. [CrossRef] [MathSciNet] [Google Scholar]
- F. Annexstein, M. Baumslag and A.L. Rosenberg, Group action graphs and parallel architectures. SIAM J. Comput. 19 (1990) 544–569. [CrossRef] [MathSciNet] [Google Scholar]
- V. Bafna and P.A. Pevzner, Sorting by transpositions. SIAM J. Discret. Math. 11 (1998) 224–240. [CrossRef] [Google Scholar]
- A. Biniaz, K. Jain, A. Lubiw, Z. Masárová, T. Miltzow, D. Mondal, A.M. Naredla, J. Tkadlec and A. Turcotte, Token swapping on trees. Discrete Math. Theor. Comput. Sci. 24 (2023) 1–37. [Google Scholar]
- É. Bonnet, T. Miltzow and P. Rzążzewski, Complexity of token swapping and its variants. Algorithmica 80 (2018) 2656–2682. [CrossRef] [MathSciNet] [Google Scholar]
- L. Bulteau, G. Fertin and I. Rusu, Pancake flipping is hard. J. Comput. Syst. Sci. 81 (2015) 1556–1574. [CrossRef] [Google Scholar]
- P. Erdös and R. Rado, A Partition Calculus in Set Theory. Birkh¨auser Boston, Boston, MA (1987) 179–241. [Google Scholar]
- D. Harel and R.E. Tarjan, Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13 (1984) 338–355. [CrossRef] [MathSciNet] [Google Scholar]
- L. Heath and J. Vergara, Sorting by short swaps. J. Comput. Biol. J. Comput. Mol. Cell Biol. 10 (2003) 775–89. [CrossRef] [PubMed] [Google Scholar]
- T. Ito, E.D. Demaine, N.J. Harvey, C.H. Papadimitriou, M. Sideri, R. Uehara and Y. Uno, On the complexity of reconfiguration problems. Theor. Comput. Sci. 412 (2011) 1054–1065. [CrossRef] [Google Scholar]
- W.W. Johnson and W.E. Story, Notes on the “15” puzzle. Am. J. Math. 2 (1879) 397–404. [CrossRef] [Google Scholar]
- J. Kawahara, T. Saitoh and R. Yoshinaka, The time complexity of the token swapping problem and its parallel variants, in WALCOM: Algorithms and Computation. Springer International Publishing, Cham (2017) 448–459. [Google Scholar]
- D.E. Knuth, The art of computer programming, in Sorting and Searching, 2nd edition. Vol. 3. Addison Wesley Longman Publishing Co., Inc., USA (1998). [Google Scholar]
- T. Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas and T. Uno, Tight exact and approximate algorithmic results on token swapping. Preprint arXiv:1602.05150 (2016). [Google Scholar]
- A.E. Mouawad, On reconfiguration problems: structure and tractability. Ph.D. thesis, University of Waterloo (2015). [Google Scholar]
- N. Nishimura, Introduction to reconfiguration. Algorithms 11 (2018) 52. [CrossRef] [Google Scholar]
- K.-J. Pai, R.-S. Chang and J.-M. Chang, Constructing dual-cists of pancake graphs and performance assessment of protection routings on some cayley networks. J. Supercomput. 76 (2020) 124546. [Google Scholar]
- A. Razborov, Proof complexity of pigeonhole principles, in Developments in Language Theory. Springer Berlin Heidelberg, Berlin, Heidelberg (2002) 100–116. [Google Scholar]
- M.Y. Siraichi, V.F.D. Santos, S. Collange and F.M.Q. Pereira, Qubit allocation, in Proceedings of the 2018 International Symposium on Code Generation and Optimization. ACM, New York, NY, USA (2018) 113–125. [Google Scholar]
- M.Y. Siraichi, V.F.D. Santos, C. Collange and F.M.Q.A. Pereira, Qubit allocation as a combination of subgraph isomorphism and token swapping. Proc. ACM Program. Lang. 3 (2019) 1–29. [CrossRef] [Google Scholar]
- J.H. Smith, Factoring, into edge transpositions of a tree, permutations fixing a terminal vertex. J. Comb. Theory Ser. A 85 (1999) 92–95. [CrossRef] [Google Scholar]
- J.H. Smith, Corrigendum to “factoring, into edge transpositions of a tree, permutations fixing a terminal vertex”. J. Comb. Theory Ser. A 118 (2011) 726–727. [CrossRef] [Google Scholar]
- J. van den Heuvel, The complexity of change, in Surveys in Combinatorics. Cambridge University Press, Cambridge (2013) 127–160. [Google Scholar]
- T.P. Vaughan, Bounds for the rank of a permutation on a tree. J. Comb. Math. Comb. Comput. 30 (1991) 129–148. [Google Scholar]
- L. Wang and K.W. Tang, The cayley graph implementation in tinyos for dense wireless sensor networks, in 2007 Wireless Telecommunications Symposium. 2007 Thyrrenian International Workshop on Digital Communication, Italy (2007) 1–7. [Google Scholar]
- K. Yamanaka, E.D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa and T. Uno, Swapping labeled tokens on graphs. Theor. Comput. Sci. 586 (2015) 81–94. [CrossRef] [Google Scholar]
- K. Yamanaka, T. Horiyama, J.M. Neil, D.G. Kirkpatrick, Y. Otachi, T. Saitoh, R. Uehara and Y. Uno, Swapping colored tokens on graphs, in Workshop on Algorithms and Data Structures. Springer, Victoria, BC, Canada (2015) 16. [Google Scholar]
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.