VeranstaltungsortN.2.01Veranstalter Institut für MathematikBeschreibungThema:Lower Bounds for the Bandwidth ProblemKurzfassung:The Bandwidth-Problem (BP) asks for a simultaneous permutation of therows and columns of the adjacency matrix of a graph such that all nonzeroentries are as close as possible to the main diagonal. It arises in manydifferent engineering applications that try to achieve efficient storage andprocessing.The BP is known to be NP-hard and also approximating the bandwidth withina given factor is known to be NP-hard. While there are several heuristicapproaches for obtaining upper bounds for the bandwidth of larger graphs,e.g., the Cuthill-McKee heuristic, there are very few results regarding lowerbounds. Most results regarding lower bounds have in common that they areunsatisfyingly weak. In general, it is much harder to obtain lower boundsthan upper bounds.Thus, this work focuses on investigating new approaches based on vertexpartitions to get lower bounds on the bandwidth. Therefore we firstintroduce the general vertex partitioning approach. Based on that, we introduceseveral Semi-Definite Programming (SDP) models in order to obtain.Vortragende(r)Christian TrudenKontaktSenka Haznadar (senka.haznadar@aau.at)