Sorting with forbidden intermediates

DOI10.1016/j.dam.2019.10.025zbMath1437.68046arXiv1602.06283OpenAlexW2984705925MaRDI QIDQ2181215

Romeo Rizzi, Stéphane Vialette, Carlo Comin, Anthony Labarre

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics, Algorithms for Computational Biology (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.06283

zbMATH Keywords

genome rearrangementpermutation sortinghypercube graphs\(st\)-connectivitylethal mutationsforbidden verticesguided sortingst-connectivity

Mathematics Subject Classification ID

Searching and sorting (68P10) Applications of graph theory (05C90) Permutations, words, matrices (05A05) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Algorithms on strings (68W32)

Related Items (1)

Sorting with forbidden intermediates

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On paths avoding forbidden pairs of vertices in a graph
• A new matching property for posets and existence of disjoint chains
• Sorting with forbidden intermediates
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Lower Bounding Edit Distances between Permutations
• Frontier search
• Optimally solving permutation sorting problems with efficient partial expansion bidirectional heuristic search
• Comparative Genomics
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Testing monotonicity
• On disjoint chains of subsets

This page was built for publication: Sorting with forbidden intermediates