René van Bevern. Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications. PhD thesis, Fakultät IV – Elektrotechnik und Informatik, TU Berlin, 2014. PhD thesis.

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.

bib | DOI | slides ] Back

This file was generated by bibtex2html 1.98.