Publikation: An Optimization-Based Sum-of-Squares Ap...
Stammdaten
Titel: | An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture |
Untertitel: | |
Kurzfassung: | Vizing's conjecture (open since 1968) relates the sizes of dominating sets in two graphs to the size of a dominating set in their Cartesian product graph. In this paper, we formulate Vizing's conjecture itself as a Positivstellensatz existence question. In particular, we encode the conjecture as an ideal/polynomial pair such that the polynomial is nonnegative if and only if the conjecture is true. We demonstrate how to use semidefinite optimization techniques to computationally obtain numeric sum-of-squares certificates, and then show how to transform these numeric certificates into symbolic certificates approving nonnegativity of our polynomial. After outlining the theoretical structure of this computer-based proof of Vizing's conjecture, we present computational and theoretical results. In particular, we present exact low-degree sparse sum-of-squares certificates for particular families of graphs. |
Schlagworte: | Vizing’s conjecture; algebraic model; Gröbner basis; sum-of-squaresproblems; semidefinite programming |
Publikationstyp: | Beitrag in Proceedings (Autorenschaft) |
Erscheinungsdatum: | 19.07.2019 (Print) |
Erschienen in: |
ISSAC '19 Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation
ISSAC '19 Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation
(
)
zur Publikation |
Titel der Serie: | - |
Bandnummer: | - |
Erstveröffentlichung: | Ja |
Version: | - |
Seite: | S. 155 - 162 |
Bild der Titelseite: |
Versionen
Keine Version vorhanden |
Erscheinungsdatum: | |
ISBN (e-book): | - |
eISSN: | - |
DOI: | http://dx.doi.org/10.1145/3326229.3326239 |
Homepage: | - |
Open Access |
|
Erscheinungsdatum: | 19.07.2019 |
ISBN: |
|
ISSN: | - |
Homepage: | https://dl.acm.org/citation.cfm?doid=3326229.3326239 |
AutorInnen
Elisabeth Gaar (intern) | ||||
Daniel Krenn (intern) | ||||
Susan Margulies
|
||||
Angelika Wiegele (intern) |
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 |
Peer Reviewed |
|
Publikationsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Organisation | Adresse | ||||
---|---|---|---|---|---|
Uppsala Universitet
|
SE - 75105 Uppsala |
||||
United States Naval Academy, Department of Mathematics
|
US Annapolis, MD |
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: |
|