Zobrazeno 1 - 10
of 11
pro vyhledávání: '"Rodrigo de A. Hausen"'
Autor:
Rodrigo de A. Hausen, Luís Felipe I. Cunha, Luis Antonio Brasil Kowada, Celina M. H. de Figueiredo
Publikováno v:
Journal of Computational Biology. 22:1044-1056
Sorting by Transpositions is an NP-hard problem for which several polynomial-time approximation algorithms have been developed. Hartman and Shamir (2006) developed a 1.5-approximation [Formula: see text] algorithm, whose running time was improved to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c749e58d722fe02bbb0cd53f973c5fce
https://doi.org/10.1089/cmb.2014.0298
https://doi.org/10.1089/cmb.2014.0298
Autor:
Luis Antonio Brasil Kowada, Rodrigo de A. Hausen, Celina M. H. de Figueiredo, Luís Felipe I. Cunha
Publikováno v:
SIAM Journal on Discrete Mathematics. 27:1682-1709
Sorting by transpositions is a challenging classic problem proposed in genome rearrangement and recently settled as NP-hard. Although the proven hard to sort $3$-permutations are close to the identity, the historical approach has been to study distan
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4311f2168abef210b7dcf4113e894528
https://doi.org/10.1137/120899753
https://doi.org/10.1137/120899753
Autor:
Candido F. X. de Mendonça, Celina M. H. de Figueiredo, Luerbio Faria, Letícia Rodrigues Bueno, Rodrigo de A. Hausen
Publikováno v:
Electronic Notes in Discrete Mathematics. 37:291-296
The Kneser graph K ( n , k ) has all k-subsets of an n-set as its vertices and two subsets are adjacent if they are disjoint. Lovasz conjectured that every connected vertex-transitive graph has a hamiltonian path. For n ⩾ 2 k + 1 , the Kneser graph
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9b12ac6d85daf3e58683bb6b4bf7648c
https://doi.org/10.1016/j.endm.2011.05.050
https://doi.org/10.1016/j.endm.2011.05.050
Publikováno v:
SIAM Journal on Discrete Mathematics. 24:792-807
H. Eriksson et al. made a breakthrough to the problem of sorting by transpositions by proposing a quotient structure named toric graph, which allowed the reduction of the search space, establishing the transposition diameter $D_t(n)=\lfloor\frac{n+1}
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::add7bbdba91eda0b4efc6f3c36af25de
https://doi.org/10.1137/08074413x
https://doi.org/10.1137/08074413x
Publikováno v:
LATIN 2014: Theoretical Informatics ISBN: 9783642544224
LATIN
LATIN
The odd graph O k is the graph whose vertices are all subsets with k elements of a set {1,…,2k + 1}, and two vertices are joined by an edge if the corresponding pair of k-subsets is disjoint. A conjecture due to Biggs claims that O k is hamiltonian
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e2b5aa7175f047970c78e3902a1d87ef
https://doi.org/10.1007/978-3-642-54423-1_33
https://doi.org/10.1007/978-3-642-54423-1_33
Autor:
Celina M. H. de Figueiredo, Luis Antonio Brasil Kowada, Luís Felipe I. Cunha, Rodrigo de A. Hausen
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783662447529
WABI
WABI
Sorting by Transpositions is an NP-hard problem for which several polynomial time approximation algorithms have been developed. Hartman and Shamir (2006) developed a 1.5-approximation algorithm, whose running time was improved to O(n logn) by Feng an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9299aade15724d657e89565e2cf7e7d3
https://doi.org/10.1007/978-3-662-44753-6_3
https://doi.org/10.1007/978-3-662-44753-6_3
Autor:
Luis Antonio Brasil Kowada, Celina M. H. de Figueiredo, Rodrigo de A. Hausen, Luís Felipe I. Cunha
Publikováno v:
Advances in Bioinformatics and Computational Biology ISBN: 9783319026237
BSB
BSB
Sorting by Transpositions is an NP-hard problem. Elias and Hartman proposed a 1.375-approximation algorithm, the best ratio so far, which runs in O(n 2) time. Firoz et al. proposed an improvement to the running time, from O(n 2) down to O(n logn), us
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6b6b4e1fc9cc827424f18e9f6f5d37df
https://doi.org/10.1007/978-3-319-02624-4_12
https://doi.org/10.1007/978-3-319-02624-4_12
Autor:
Rodrigo de A. Hausen, Luis Antonio Brasil Kowada, Celina M. H. de Figueiredo, Luís Felipe I. Cunha
Publikováno v:
Advances in Bioinformatics and Computational Biology ISBN: 9783642319266
BSB
BSB
Determining the transposition distance of permutations was proven recently to be \(\textup{NP}\)-hard. However, the problem of the transposition diameter is still open. The known lower bounds for the diameter were given by Meidanis, Walter and Dias w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3f43b7c7f99698fda39407a356b47aab
https://doi.org/10.1007/978-3-642-31927-3_1
https://doi.org/10.1007/978-3-642-31927-3_1
Autor:
Marcelo P. Lopes, Celina M. H. de Figueiredo, Marília D. V. Braga, Luis Antonio Brasil Kowada, Rodrigo de A. Hausen
Publikováno v:
Advances in Bioinformatics and Computational Biology ISBN: 9783642228247
BSB
BSB
Feng and Zhu defined the permutation tree structure to achieve a running time of O(n log n) for Hartman and Shamir's 1.5- approximation algorithm for sorting genomes by transpositions. The present work describes the first available implementation of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4fd57369af61a7d2ec7d4f28d7fde1de
https://doi.org/10.1007/978-3-642-22825-4_6
https://doi.org/10.1007/978-3-642-22825-4_6
Publikováno v:
Advances in Bioinformatics and Computational Biology ISBN: 9783642150593
BSB
BSB
The problem of determining the transposition distance of permutations is a notoriously challenging one; to this date, neither there exists a polynomial algorithm for solving it, nor a proof that it is NPhard. Moreover, there are no tight bounds on th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::591bc1499f0cf6b5c2c51365a6f34df8
https://doi.org/10.1007/978-3-642-15060-9_4
https://doi.org/10.1007/978-3-642-15060-9_4