Stephan Matos Camacho

Introduction to the Minimum Rainbow Subgraph problem

Dokumente und Dateien

Hinweis

Bitte nutzen Sie beim Zitieren immer folgende Url:

http://nbn-resolving.de/urn:nbn:de:bsz:105-qucosa-85490

Kurzfassung in Englisch

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.

weitere Metadaten

übersetzter Titel
(Deutsch)
Einführung in das Minimum Rainbow Subgraph Problem
Schlagwörter
(Deutsch)
Graphentheorie, Kantenfärbung, Haplotyping, Bioinformatik
Schlagwörter
(Englisch)
graph theory, edge colouring, haplotyping, bioinformatics
SWD SchlagworteKantenfärbung, Haplotyp, Analyse, Bioinformatik
DDC Klassifikation510
Institution(en) 
HochschuleTU Bergakademie Freiberg
FakultätMathematik und Informatik
InstitutInstitut für Diskrete Mathematik und Algebra
BetreuerProf. Dr. rer. nat. habil. Ingo Schiermeyer
GutachterProf. Dr. rer. nat. habil. Ingo Schiermeyer
Prof. Dr. rer. nat. habil. Hubert Randerath
DokumententypDissertation
SpracheEnglisch
Tag d. Einreichung (bei der Fakultät)16.01.2012
Tag d. Verteidigung / Kolloquiums / Prüfung13.03.2012
Veröffentlichungsdatum (online)27.03.2012
persistente URNurn:nbn:de:bsz:105-qucosa-85490
InhaltsverzeichnisMathematics and biology - having nothing in common?
I. Going for a start
1. Introducing haplotyping
2. Becoming mathematical
II. The MRS problem
3. The graph theoretical point of view
3.1. The MRS problem
3.2. The MRS problem on special graph classes
4. Trying to be not that bad
4.1. Greedy approaches
4.2. The local colour density
4.3. MaxNewColour
5. What is real data telling us?
And the work goes on and on
Bibliography

Hinweis zum Urheberrecht

Diese Website ist eine Installation von Qucosa - Quality Content of Saxony!
Sächsische Landesbibliothek Staats- und Universitätsbibliothek Dresden