Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Sorting by short swaps.

Lenwood S Heath1, John Paul C Vergara

  • 1Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061-0106, USA. heath@vt.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|November 25, 2003
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

ViraFit: Tunable Fitness Model for Viral Evolution Within a Contact Network.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same author

Comparative genomics of human brain and immune gene preservation across species.

PloS one·2026
Same author

Genomic insights into <i>Ceratobasidium</i> sp. associated with vascular streak dieback of woody ornamentals in the United States using a metagenomic sequencing approach.

Microbiology spectrum·2026
Same author

Reflections on the Presence of Human Cancer Genes in Primate Genomes.

Journal of computational biology : a journal of computational molecular cell biology·2025
Same author

Variant evolution graph: Can we infer how SARS-CoV-2 variants are evolving?

PloS one·2025
Same author

LINgroups as a Robust Principled Approach to Compare and Integrate Multiple Bacterial Taxonomies.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Mosquito Species and Gender Identification System Based on Artificial Intelligence and Image Processing Methods.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

This study introduces a 2-approximation algorithm for sorting permutations using short swaps. It also establishes bounds for the short-swap diameter, a key metric in permutation sorting.

Area of Science:

  • Combinatorics
  • Computer Science
  • Discrete Mathematics

Background:

  • Permutations are fundamental in mathematics and computer science.
  • Sorting permutations efficiently is a significant computational challenge.
  • Short swaps offer a specific constraint for permutation manipulation.

Purpose of the Study:

  • To investigate the problem of finding minimum-length sorting sequences using short swaps.
  • To develop an efficient algorithm for this sorting problem.
  • To determine bounds for the short-swap diameter.

Main Methods:

  • Introduced a polynomial-time 2-approximation algorithm.
  • Analyzed the properties of short swaps in permutation sorting.
  • Derived bounds for the short-swap diameter.

Related Experiment Videos

Main Results:

  • A 2-approximation algorithm for minimum-length short swap sorting was developed.
  • Theoretical bounds for the short-swap diameter were obtained.
  • The algorithm provides an efficient approach to a complex sorting problem.

Conclusions:

  • The research provides an efficient algorithmic solution for sorting permutations with short swaps.
  • The established bounds offer insights into the complexity of permutation sorting via short swaps.
  • This work contributes to the understanding of permutation group theory and sorting algorithms.