20 citations · 28 across the 6 of their papers we have counts for
6 papers
Connectivity via convexity: Bounds on the edge expansion in graphs
Timotej Hrga, Melanie Siebenhofer, Angelika Wiegele
Convexification techniques have gained increasing interest over the past decades. In this work, we apply a recently developed convexification technique for fractional programs by H…
Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem
Frank de Meijer, Melanie Siebenhofer, Renata Sotirov +1
In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation…
Edge expansion of a graph: SDP-based computational strategies
Akshay Gupte, Melanie Siebenhofer, Angelika Wiegele
Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms u…
Sum-of-Squares Certificates for Vizing's Conjecture via Determining Gröbner Bases
Elisabeth Gaar, Melanie Siebenhofer
The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs and is at least the product of the domination numbers of $G…
An SDP-Based Approach for Computing the Stability Number of a Graph
Elisabeth Gaar, Melanie Siebenhofer, Angelika Wiegele
Finding the stability number of a graph, i.e., the maximum number of vertices of which no two are adjacent, is a well known NP-hard combinatorial optimization problem. Since this p…
BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints
Nicolò Gusmeroli, Timotej Hrga, Borut Lužar +3
We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original…