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. It is the optimal value of a semidefinite program in matrices of order n having m equality constraints plus possibly some additional sign constraints. Here n denotes the number of vertices and m the number of edges of the underlying graph. 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: |
Typ: | Gastvortrag |
Homepage: | https://oglasi.matf.bg.ac.rs/seminar-za-racunarstvo-i-primenjenu-matematiku-20-decembar-2022/ |
Veranstaltung: | Seminar in Computer Science and Applied Mathematics (Beograd) |
Datum: | 20.12.2022 |
Vortragsstatus: | stattgefunden (online) |
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Vortragsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
TeilnehmerInnenkreis |
|
Publiziert? |
|
Arbeitsgruppen |
|
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte |
|
Publikationen | Keine verknüpften Publikationen vorhanden |
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge | Keine verknüpften Vorträge vorhanden |