Vortrag: Strengthening of the semidefinite relaxation for graph coloring probl...

Stammdaten
Titel: Strengthening of the semidefinite relaxation for graph coloring problem
Beschreibung:

The Lovász Theta function provides a well studied tool to get bounds for the chromatic number of graphs. We propose a further tightening of this bound using the exact subgraph idea in a new way. Rather than looking at subgraphs with a small number of vertices which should be contained in the respective polytope, we now consider subgraphs with certain structure and require them to be contained in the corresponding polytope. We compare our bounds with relaxations given by Szegedy and Meurdesoif and present computational results.
Schlagworte: colloquium of doctoral school, multiperspective scientific exchange
Typ: Angemeldeter Vortrag
Homepage: -
Veranstaltung: Second status seminar (Alpen Adria Universität Klagenfurt)
Datum: 07.10.2022
Vortragsstatus: stattgefunden (Präsenz)

Beteiligte
Dunja Pucher
Dunja.Pucher@aau.at
Institut für Mathematik
Forschungsaktivitäten
zur Visitenkarte
(intern)
  • Vortragende/r

Zuordnung
Organisation Adresse
Fakultät für Technische Wissenschaften
  Institut für Mathematik
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Österreich
   math@aau.at
https://www.aau.at/mathematik
zur Organisation
Universitätsstraße 65-67
AT - 9020  Klagenfurt am Wörthersee

Kategorisierung
Sachgebiete
  • 101016 - Optimierung
Forschungscluster Kein Forschungscluster ausgewählt
Vortragsfokus
  • Science to Science (Qualitätsindikator: III)
Klassifikationsraster der zugeordneten Organisationseinheiten:
TeilnehmerInnenkreis
  • Überwiegend national
Publiziert?
  • Nein
Arbeitsgruppen
  • Optimierung

Kooperationen
Keine Partnerorganisation ausgewählt