Adamson, Duncan 
ORCID: 0000-0003-3343-2435, Flaherty, Nathan ORCID: 0000-0002-2798-4084, Potapov, Igor ORCID: 0000-0002-7192-7853 and Spirakis, Paul G ORCID: 0000-0001-5396-3749
(2024)
Structural and Combinatorial Properties of 2-Swap Word Permutation Graphs.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 14579 .
pp. 61-76.
|
PDF
Swaps_paper.pdf - Submitted version Download (389kB) | Preview |
Abstract
In this paper, we study the graph induced by the 2-swap permutation on words with a fixed Parikh vector. A 2-swap is defined as a pair of positions s=(i,j) where the word w induced by the swap s on v is v[1]v[2]⋯v[i-1]v[j]v[i+1]⋯v[j-1]v[i]v[j+1]⋯v[n]. With these permutations, we define the Configuration Graph, G(P) for a given Parikh vector. Each vertex in G(P) corresponds to a unique word with the Parikh vector P, with an edge between any pair of words v and w if there exists a swap s such that v∘s=w. We provide several key combinatorial properties of this graph, including the exact diameter of this graph, the clique number of the graph, and the relationships between subgraphs within this graph. Additionally, we show that for every vertex in the graph, there exists a Hamiltonian path starting at this vertex. Finally, we provide an algorithm enumerating these paths from a given input word of length n with a delay of at most O(logn) between outputting edges, requiring O(nlogn) preprocessing.
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 12 Dec 2023 08:27 |
| Last Modified: | 05 Apr 2024 23:50 |
| DOI: | 10.1007/978-3-031-55601-2_5 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3177264 |
Dimensions
Dimensions
