The Number Of Unique-Sink Orientations of the Hypercube*
The Number Of Unique-Sink Orientations of the Hypercube*
复制标题
超立方体独特水槽方向的数量*
DOI：
10.1007/s00493-006-0007-0
复制
发表时间：
2006
期刊：
影响因子：
1.1
通讯作者：
J. Matoušek
中科院分区：
文献类型：
--
作者：
J. Matoušek
令Qd表示d维立方体的图。唯一汇方向（USO）是 Qd 的一种方向，使得 Qn 的每个面都恰好有一个汇（出度为 0 的顶点）；它不必是非循环的。 USO 已作为许多几何优化问题的抽象模型进行研究，例如线性规划、查找给定点集的最小包围球、某些类别的凸规划以及某些线性互补问题。由此可见，USO 的数量为。
LetQddenote the graph of thed-dimensional cube. Aunique-sink orientation(USO) is an orientation ofQdsuch that every face ofQnhas exactly one sink (vertex of out degree 0); it does not have to be acyclic. USO have been studied as an abstract model for many geometric optimization problems, such as linear programming, finding the smallest enclosing ball of a given point set, certain classes of convex programming, and certain linear complementarity problems. It is shown that the number of USO is.