Lade Veranstaltungen

« All Events

  • Diese Veranstaltung hat bereits stattgefunden.

Vortrag im Rahmen des Doctoral Seminar in Mathematics von Herrn Christian Truden

16. Januar 2019 um 11:00

Veranstaltungskategorie Vortrag |Foto: kasto/Fotolia.com

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.haznadar [at] aau.at)

Details

Termine:
16. Januar 2019 um 11:00 Uhr
Veranstaltungskategorie:
zum Veranstaltungskalender