Arisen from the Pure Parsimony Haplotyping problem in the bioinformatics, we developed the Minimum Rainbow Subgraph problem (MRS problem): Given a graph $G$, whose edges are coloured with $p$ colours. Find a subgraph $F\\\\subseteq G$ of $G$ of minimum order and with $p$ edges such that each colour occurs exactly once. We proved that this problem is NP-hard, and even APX-hard. Furthermore, we stated upper and lower bounds on the order of such minimum rainbow subgraphs. Several polynomial-time approximation algorithms concerning their approximation ratio and complexity were discussed. Therefore, we used Greedy approaches, or introduced the local colour density $\\\\lcd(T,S)$, giving a ratio on the number of colours and the number of vertices between two subgraphs $S,T\\\\subseteq G$ of $G$. Also, we took a closer look at graphs corresponding to the original haplotyping problem and discussed their special structure.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:105-qucosa-85490 |
| Date | 27 March 2012 |
| Creators | Matos Camacho, Stephan |
| Contributors | TU Bergakademie Freiberg, Mathematik und Informatik, Prof. Dr. rer. nat. habil. Ingo Schiermeyer, Prof. Dr. rer. nat. habil. Ingo Schiermeyer, Prof. Dr. rer. nat. habil. Hubert Randerath |
| Publisher | Technische Universitaet Bergakademie Freiberg Universitaetsbibliothek "Georgius Agricola" |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis |
| Format | application/pdf |
Page generated in 0.0286 seconds