9 citations · 50 across the 22 of their papers we have counts for
5 papers · 1 filter
A Computational Study of Exact Subgraph Based SDP Bounds for Max-Cut, Stable Set and Coloring
Elisabeth Gaar, Franz Rendl
The "exact subgraph" approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization…
A characterization of graphs with regular distance- graphs
Elisabeth Gaar, Daniel Krenn
For non-negative integers~, we consider graphs in which every vertex has exactly vertices at distance~, i.e., graphs whose distance- graphs are -regular. We call su…
Towards a Computational Proof of Vizing's Conjecture using Semidefinite Programming and Sums-of-Squares
Elisabeth Gaar, Daniel Krenn, Susan Margulies +1
Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formu…
On different Versions of the Exact Subgraph Hierarchy for the Stable Set Problem
Elisabeth Gaar
Let be a graph with vertices and edges. One of several hierarchies towards the stability number of is the exact subgraph hierarchy (ESH). On the first level it comp…
On -Bend and Monotonic -Bend Edge Intersection Graphs of Paths on a Grid
Eranda Çela, Elisabeth Gaar
If a graph can be represented by means of paths on a grid, such that each vertex of corresponds to one path on the grid and two vertices of are adjacent if and only if…