Vortrag im Rahmen des Doctoral Seminar in Mathematics von Herrn Christian Truden
Veranstaltungsort
N.2.01
Veranstalter
Institut für Mathematik
Beschreibung
Thema:
Lower Bounds for the Bandwidth Problem
Kurzfassung:
The Bandwidth-Problem (BP) asks for a simultaneous permutation of the
rows and columns of the adjacency matrix of a graph such that all nonzero
entries are as close as possible to the main diagonal. It arises in many
different engineering applications that try to achieve efficient storage and
processing.
The BP is known to be NP-hard and also approximating the bandwidth within
a given factor is known to be NP-hard. While there are several heuristic
approaches for obtaining upper bounds for the bandwidth of larger graphs,
e.g., the Cuthill-McKee heuristic, there are very few results regarding lower
bounds. Most results regarding lower bounds have in common that they are
unsatisfyingly weak. In general, it is much harder to obtain lower bounds
than upper bounds.
Thus, this work focuses on investigating new approaches based on vertex
partitions to get lower bounds on the bandwidth. Therefore we first
introduce the general vertex partitioning approach. Based on that, we introduce
several Semi-Definite Programming (SDP) models in order to obtain.
Vortragende(r)
Christian Truden
Kontakt
Senka Haznadar (senka [dot] haznadar [at] aau [dot] at)
Ähnliche Veranstaltungen
