Quantum Algorithms for One-Sided Crossing Minimization

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista

We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an $n$-vertex bipartite graph $G=(U,V,E\subseteq U\times V)$, a $2$-…