NY DOKTORGRAD

Parallell graf-fargelegging

Cand. scient. Assefaw Hadish Gebremedhin disputerer tirsdag 25. mars 2003 for dr.scient. graden ved Universitetet i Bergen med avhandlingen:

"Practical Parallel Algorithms for Graph Coloring Problems in Numerical Optimization".

I 1852 påstod engelskmannen Francis Guthrie at fire farger er nok for å fargelegge et hvilket som helst kart slik at ingen naboland får samme farge. Påstanden utfordret matematikere lenge, inntil det i 1976 ble bevist. Selv om tidligere bevisforsøk var mislykket bidro de til utviklingen av fagområdet graf-teori.

Graf-fargeleggingsproblemet går generelt ut på å dele opp et set av objekter i minst mulig antall grupper slik at visse regler er oppfylt. Dette problemet er meget sentralt innenfor både matematikk og informatikk. Problemet oppstår i ulike sammenhenger med begrensete resurser, blant annet i frekvenstildeling til mobiltelefoner, testing av
kretskort, parallell databehandling, og numeriske beregninger.

I avhandlingen ser Gebremedhin primært på hvordan ulike varianter av fargeleggingsproblemet kan løses på moderne kraftige parallelle datamaskiner. Han har utviklet flere nye metoder som gjennom praktiske storskala forsøk har
vist seg å være effektive. Det er lagt særlig vekt på anvendelse av fargeleggingsproblemet innen numerisk optimering, hvor målet er å beregne glisne
første- og andrederiverte matriser på en effektiv måte.

For å kunne utføre arbeidet har det vært nødvendig å studere og å videreutvikle
eksisterende parallelle beregningsmodeller. Som et resultat av dette er det også
blitt utviklet en ny beregningsmodell som i større grad enn tidligere knytter sammen
teori og praksis.

Personalia:
Assefaw Hadish Gebremedhin (32) er født og oppvokst i Etiopia. Han tok B.Sc. graden i Electrical Engineering ved Addis Ababa University i 1992. Siden 1994 har han studert ved Universitet i Bergen hvor han avla hovedfagseksamen i informatikk i mai 1999. Siden september 1999 har han vært ansatt som universitetsstipendiat ved Institutt for informatikk, UiB.

Tidspunkt og sted for disputasen:
25.03.2003, kl. 12:15, Stort auditorium, rom 2144, Datablokken, Høyteknologisenteret, Thormøhlensgt. 55

Kontaktpersoner:
Assefaw Hadish Gebremedhin, tlf. 55584271 (a), 55136267 (p), epost: assefaw@ii.uib.no
Formidlingsavdelingen v/ mediekontakt Ingunn Vie Skare, tlf. 55 58 91 70 (a),
epost: ingunn.skare@form.uib.no

Avhandlingen kan lånes på Det matematisk-naturvitenskapelige fakultetsbibliotek. For kjøp/bestilling: kontakt kandidaten direkte.