A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Graph theoretic approach to parallel gene assembly
Tekijät: Harju T, Li C, Petre I
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2008
Lehti:Discrete Applied Mathematics
Tietokannassa oleva lehden nimiDISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 156
Numero: 18
Aloitussivu: 3416
Lopetussivu: 3429
Sivujen määrä: 14
ISSN: 0166-218X
DOI: https://doi.org/10.1016/j.dam.2008.01.022
Tiivistelmä
We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or - In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs call be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic. (C) 2008 Elsevier B.V. All rights reserved.
We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or - In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs call be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic. (C) 2008 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali