## 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.*