2 citations · 2 across the 6 of their papers we have counts for
6 papers
Quantum and Simulated Annealing-Based Iterative Algorithms for QUBO Relaxations of the Sparsest -Subgraph Problem
Omkar Bihani, Roman Kužel, Janez Povh +1
In this paper, we introduce three QUBO (Quadratic Unconstrained Binary Optimization) relaxations for the sparsest -subgraph (SkS) problem: a quadratic penalty relaxation, a Lagr…
The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
Elisabeth Gaar, Dunja Pucher
The stability number of a graph, defined as the cardinality of the largest set of pairwise non-adjacent vertices, is NP-hard to compute. The exact subgraph hierarchy (ESH) provides…
Quantum computing and the stable set problem
Aljaž Krpan, Janez Povh, Dunja Pucher
Given an undirected graph, the stable set problem asks to determine the cardinality of the largest subset of pairwise non-adjacent vertices. This value is called the stability numb…
Practical Experience with Stable Set and Coloring Relaxations
Dunja Pucher, Franz Rendl
The stable set problem and the graph coloring problem are classes of NP-hard optimization problems on graphs. It is well known that even near-optimal solutions for these problems a…
Advancing stable set problem solutions through quantum annealers
Janez Povh, Dunja Pucher
We assess the performance of D-wave quantum solvers for solving the stable set problem in a graph, one of the most studied NP-hard problems. We perform computations on some instanc…
Stable-Set and Coloring bounds based on 0-1 quadratic optimization
Dunja Pucher, Franz Rendl
We consider semidefinite relaxations of Stable-Set and Coloring, which are based on quadratic 0-1 optimization. Information about the stability number and the chromatic number is h…