Conference
Average-case analysis of perfect sorting by reversals
| العنوان: | Average-case analysis of perfect sorting by reversals |
|---|---|
| المؤلفون: | Bouvel, Mathilde, Chauve, Cedric, Mishna, Marni, Rossin, Dominique |
| المساهمون: | Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics Burnaby (SFU), Simon Fraser University = Université Simon Fraser (SFU.ca), ANR-07-BLAN-0002,M3,Model and measurement of meaning: A cross-lingual and multi-disciplinary approach of French and Mandarin verbs based on distance in paradigmatic graphs(2007) |
| المصدر: | ISSN: 0302-9743 ; Lecture Notes in Computer Science. |
| بيانات النشر: | HAL CCSD Springer |
| سنة النشر: | 2009 |
| مصطلحات موضوعية: | Sorting by reversals, Interval-Decomposition, Permutations, MSC : 05A05, 05A16, 05C90, 05C05, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], [SDV.BIBS]Life Sciences [q-bio]/Quantitative Methods [q-bio.QM] |
| جغرافية الموضوع: | Lille, France |
| الوصف: | International audience ; A sequence of reversals that takes a signed permutation to the identity is perfect if at no step a common interval is broken. Determining a parsimonious perfect sequence of reversals that sorts a signed permutation is NP-hard. Here we show that, despite this worst-case analysis, with probability one, sorting can be done in polynomial time. Further, we find asymptotic expressions for the average length and number of reversals in commuting permutations, an interesting sub-class of signed permutations. |
| نوع الوثيقة: | conference object |
| اللغة: | English |
| Relation: | info:eu-repo/semantics/altIdentifier/arxiv/0901.2847; hal-00354235; https://hal.science/hal-00354235; https://hal.science/hal-00354235/document; https://hal.science/hal-00354235/file/HAL.pdf; ARXIV: 0901.2847 |
| DOI: | 10.1007/978-3-642-02441-2_28 |
| الاتاحة: | https://hal.science/hal-00354235 https://hal.science/hal-00354235/document https://hal.science/hal-00354235/file/HAL.pdf https://doi.org/10.1007/978-3-642-02441-2_28 |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.D5C6F0A4 |
| قاعدة البيانات: | BASE |
| DOI: | 10.1007/978-3-642-02441-2_28 |
|---|