Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-4131
Main Title: Fixed-parameter linear-time algorithms for NP-hard graph and hypergraph problems arising in industrial applications
Translated Title: Festparameter-Linearzeitalgorithmen für NP-schwere Graphen- und Hypergraphenprobleme aus industriellen Anwendungen
Author(s): Bevern, René van
Advisor(s): Niedermeier, Rolf
Referee(s): Fomin, Fedor V.
Möhring, Rolf
Niedermeier, Rolf
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Diese Dissertation beschäftigt sich mit der Entwicklung effizienter Algorithmen zur exakten Lösung vier ausgewählter NP-schwerer Probleme aus der Ablaufplanung, Stahlverarbeitung, Softwaretechnik, Frequenzzuteilung, aus der computergestützten Hardwareentwicklung und der Analyse sozialer Netzwerke. NP-schwere Probleme können vermutlich nicht optimal in einer polynomiell mit der Eingabegröße wachsenden Zeit gelöst werden. Um sie dennoch effizient zu lösen, entwickelt diese Arbeit Linearzeitdatenreduktionsalgorithmen und Festparameter-Linearzeitalgorithmen – Algorithmen, die beweisbar in Linearzeit laufen, wenn bestimmte Parameter der Probleminstanzen konstant sind. Hierbei wird nicht nur bewiesen, dass die entwickelten Algorithmen in Linearzeit laufen, es findet zusätzlich eine experimentelle Evaluation der meisten der entwickelten Algorithmen statt. Ferner werden die Grenzen von Festparameter-Linearzeitalgorithmen und beweisbar effizienter und effektiver Datenreduktion aufgezeigt.
This thesis aims for the development of efficient algorithms to exactly solve four selected NP-hard graph and hypergraph problems arising in the fields of scheduling, steel manufactoring, software engineering, radio frequency allocation, computer-aided circuit design, and social network analysis. NP-hard problems presumably cannot be solved exactly in a running time growing only polynomially with the input size. In order to still solve the considered problems efficiently, this thesis develops linear-time data reduction and fixed-parameter linear-time algorithms—algorithms that can be proven to run in linear time if certain parameters of the problem instances are constant. Besides proving linear worst-case running times, the efficiency of most of the developed algorithms is evaluated experimentally. Moreover, the limits of fixed-parameter linear-time algorithms and provably efficient and effective data reduction are shown.
URI: urn:nbn:de:kobv:83-opus4-55292
http://depositonce.tu-berlin.de/handle/11303/4428
http://dx.doi.org/10.14279/depositonce-4131
Exam Date: 17-Jun-2014
Issue Date: 2-Oct-2014
Date Available: 2-Oct-2014
DDC Class: 004 Datenverarbeitung; Informatik
510 Mathematik
Subject(s): Ablaufplanung
Automaten
Clustering
Datenreduktion
Exakte Algorithmen
Automata
Clustering
Data reduction
Exact algorithms
Scheduling
Usage rights: Terms of German Copyright Law
Series: Foundations of computing
Series Number: 1
ISBN: 978-3-7983-2706-1
ISSN: 2199-5257
Notes: Zugleich gedruckt erschienen im Universitätsverlag der TU Berlin unter der ISBN 978-3-7983-2705-4; ISSN 2199-5249
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
bevern_rene_van.pdf2.69 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.