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

## Veranstaltungszeiten

16.01.2019, 11:00 -

## Veranstaltungsort

Raum: N.2.01

Hauptgebäude, NordTrakt West Ebene 2

## Veranstalter

Institut für Mathematik

## Kurzfassung

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.