Twin-width and permutations
EUROCOMB’23
156–162
Albert, M., Bouvel, M., & Féray, V. (2020) Two first-order logics of permutations. Journal of Combinatorial Theory, Series A, 171, 105158.
https://doi.org/10.1016/j.jcta.2019.105158
Bernardi, O., Noy, M., & Welsh, D. (2010) Growth constants of minor-closed classes of graphs. Journal of Combinatorial Theory, Series B, 100, 468-484.
https://doi.org/10.1016/j.jctb.2010.03.001
Bonnet, É., Geniet, C., Kim, E.J., Thomassé, S., & Watrigant, R. (2021a) Twin-width II: small classes. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 1977-1996.
https://doi.org/10.1137/1.9781611976465.118
Bonnet, É., Geniet, C., Kim, E.J., Thomassé, S., & Watrigant, R. (2021b) Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), vol. 198, LIPIcs (Bansal, N., Merelli, E., & Worrell, J. eds). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 35:1-35:20.
Bonnet, É., Kim, E.J., Thomassé, S., & Watrigant, R. (2020) Twin-width I: tractable FO model checking. 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020. IEEE, pp. 601-612.
https://doi.org/10.1109/FOCS46700.2020.00062
Bonnet, É., Giocanti, U., Ossona de Mendez, P., Simon, P., Thomassé, S., & Toruńczyk, S. (2021) Twin-width IV: ordered graphs and matrices.
https://doi.org/10.1145/3519935.3520037
Bonnet, É., Nešetřil, J., Ossona de Mendez, P., Siebertz, S., & Thomassé, S. (2021) Twin-width and permutations.
Colcombet, T. (2007) A Combinatorial Theorem for Trees. Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, vol. 4596, Lecture Notes in Computer Science (Arge, L., Cachin, C., Jurdzinski, T., & Tarlecki, A. eds). Springer, pp. 901-912.
https://doi.org/10.1007/978-3-540-73420-8_77
Guillemot, S. & Marx, D. (2014) Finding small patterns in permutations in linear time. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014. pp. 82-101.
https://doi.org/10.1137/1.9781611973402.7
Marcus, A. & Tardos, G. (2004) Excluded permutation matrices and the Stanley-Wilf conjecture. J. Comb. Theory, Ser. A, 107, 153-160.
https://doi.org/10.1016/j.jcta.2004.04.002
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Édouard Bonnet, Jaroslav Nesetril, Patrice Ossona de Mendez, Sebastian Siebertz, Stephan Thomassé