Martin Zachariasen udgiver ny bog om Steinertræ-problemet – Københavns Universitet

Datalogisk Institut, DIKU > Nyheder > DIKU-nyheder 2015 > Martin Zachariasen udg...

05. maj 2015

Martin Zachariasen udgiver ny bog om Steinertræ-problemet

Forskning, Steinertræ

DIKUs forhenværende institutleder, Martin Zachariasen, har netop udgivet en ny bog on Steinertræ-problemet med titlen Optimal Interconnection Trees in the Plane.

Martin Zachariasen startede på sit nye job som dekan for det Naturvidenskabelige Fakultet på Syddansk Universitet mandag d. 4. maj 2015. Men i mange år inden da havde han en travl hverdag som Institutleder for Datalogisk Institut på Københavns Universitet (DIKU).

På trods af travlhed og ansvar præsterede han samtidig med lederjobbet på DIKU at skrive og forsvare sin doktordissputats om Steinertræer, som nu er blevet til kernen i ét af de 4 hovedkapitler i bogen, Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications, som blev udgivet på forlaget Springer i 2015 med Marcus Brazil som medforfatter.

Martin Zachariasen fortæller om bogen

- Historien bag bogen er den, at jeg i 2010 forsvarede min doktordisputats om Steinertræ-problemet med såkaldte faste retninger. Efter disputatsforsvaret foreslog begge opponenter, prof. Ronald Graham og prof. Jens Vygen, at jeg skrev en bog om emnet. Jeg valgte at alliere mig med min gode kollega fra University of Melbourne, prof. Marcus Brazil, og vi gik i gang med projektet i 2011. Vi kontaktede Springer, og de udviste interesse for at publicere bogen i en af deres velkendte bogserier.

- Bogen kom til at omhandle de forskellige varianter af Steinertræ-problemet i et plan. Materiale fra min doktordisputats kom til at udgøre et af 4 hovedkapitler i bogen. 

- Marcus og jeg valgte, at bogen skulle være “selfcontained”, så den indeholder alle centrale matematiske beviser vedrørende Steinertræers egenskaber, herunder algoritmer til at løse problemet. Vi har også gjort os stor umage med at udarbejde mange figurer i høj kvalitet, og vi har også valgt - og fået lov til fra forlaget - at bruge farver til de fleste figurer. Dette burde gøre læsningen af bogen nemmere. 

- Bogen indeholder en række detaljer, som ikke tidligere er udkommet i bogform, bl.a

  • en betydeligt opdateret beskrivelse af problemernes historiske oprindelse
  • komplette beviser for problemernes NP-hårdhed
  • detaljerede beskrivelser af de meste relevante eksakte algoritmer.

Bogen kan bestilles på springer.com