Facility location and clock tree synthesis [Elektronische Ressource] / vorgelegt von Jens Uwe Maßberg

Facility LocationandClock Tree SynthesisDissertationzur Erlangung des Doktorgradesder Mathematisch-Naturwissenschaftlichen Fakult¨atder Rheinischen Friedrich-Wilhelms-Universit¨at Bonnvorgelegt vonJens Uwe Maßbergaus Hannoverim Oktober 2009AngefertigtmitGenehmigungderMathematisch-NaturwissenschaftlichenFakult¨atderRheinischen Friedrich-Wilhelms-Universit¨at BonnDiese Disseratation ist auf dem Hochschulschriftenserver der ULB Bonn unterhttp://hss.ulb.uni-bonn.de/diss online elektronisch publiziert.Erscheinungsjahr: 2010Erstgutachter: Prof. Dr. Jens VygenZweitgutachter: Prof. Dr. Dr. h.c. Bernhard KorteTag der Promotion: 18.12.2009ContentsIntroduction 11 The Sink Clustering Problem 51.1 Problem and Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . 51.1.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.3 The Sink Clustering Algorithm . . . . . . . . . . . . . . . . . . 71.1.4 Variants of the Sink Clustering Algorithm . . . . . . . . . . . . 111.1.5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.2 Post Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2.1 TwoClusterOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2.2 ChainOpt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.