论文标题
NP-固定树问题的QUBO配方
QUBO formulations for NP-Hard spanning tree problems
论文作者
论文摘要
我们引入了一种新型的二次无约束二进制优化（QUBO）公式方法，用于跨越树问题。我们选择编码跨越树作为排列问题的编码，而不是单独编码树中的存在。我们将方法应用于四个NP跨越树的变体，即K-mimimum跨度树，程度约束的最小生成树，最小叶子生成树和最大的叶子生成树。我们的主要结果是使用$ \ Mathcal {O}（| V | K）的公式，用于K-Mimumimum跨度树问题，击败需要$ \ Mathcal {o}的相关策略（| V |^{2}）$变量。
We introduce a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation method for spanning tree problems. Instead of encoding the presence of edges in the tree individually, we opt to encode spanning trees as a permutation problem. We apply our method to four NP-hard spanning tree variants, namely the k-minimum spanning tree, degree-constrained minimum spanning tree, minimum leaf spanning tree, and maximum leaf spanning tree. Our main result is a formulation with $\mathcal{O}(|V|k)$ variables for the k-minimum spanning tree problem, beating related strategies that need $\mathcal{O}(|V|^{2})$ variables.
