Graph-based AlgorithmsforPareto PreferenceQuery EvaluationDissertation zur Erlangung des Grades einesDoktors der Naturwissenschaften (Dr. rer. nat)der Fakult¨at fu¨r Angewandte Informatikder Universit¨at AugsburgTimotheus PreisingerUniversity of AugsburgHGOU0NMROCKABSGutachter:Erstgutachter: Prof. Dr. Werner KießlingZweitgutachter: Prof. Dr. Bernhard M¨ollerMu¨ndliche Pru¨fung: 9. Juli 2009Bibliografische Information der Deutschen NationalbibliothekDie Deutsche Nationalbibliothek verzeichnet diese Publikation in derDeutschenNationalbibliografie;detailliertebibliografischeDatensindimInternet u¨ber http://dnb.d-nb.de abrufbar.© 2009 Timotheus PreisingerHerstellung und VerlagBooks on Demand GmbH, NorderstedtISBN: 978-3-8391-2011-8To my family and my friends.I would like to thank everybody who supported me during the last years– may it have been by expertise or boosting morale or mood.My friends who spent countless hours with me listening to bands in shabby clubs andat muddy music festivals (as well as shiny clubs and sunny music festivals).All the unknown people entertaining me or letting me entertain them.You all did what you could to distract me from doing research.I would not have come this far without you!Thank you all!CONTENTSContents1 Introduction 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Objectives of this Book . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.