在翻转边缘设置在独特的水槽定向.

科学领域:

• 图形理论 图形理论
• 组合学是一种组合学.
• 计算几何学的计算几何学

背景情况:

• 在离散几何学和图形理论中,独特的水槽定向 (USO) 是基本的,特别是关于超立方图的定向.
• 在USO上的翻转图是关键结构,允许在不同的USO配置之间进行转换.
• 舒尔定理为理解特定维度的USO边缘内的相分解提供了理论基础.

研究的目的:

• 开发一种高效的算法来计算给定的n维USO的相位.
• 在USO翻转图中分析翻转相的空间复杂性.
• 调查通过布尔回路编码的USO确定阶段成员的计算复杂性.

主要方法:

• 开发了一种新的算法,可以在O(n^2) 时间内计算USO的相位.
• 分析了空间复杂性,显示相反转只需要多 (n) 个额外的空间.
• 确定了确定两个边缘是否属于电路编码USO的同一阶段的co-NP-completeness.

主要成果:

• 一个O(n^2) 算法用于计算USO阶段,这与之前的O(n^3) 微不足道算法相比是一个显著的改进.
• 证明翻转一个相位只需要多 (n) 个辅助空间.
• 证明了决定电路编码USO的相等性是co-NP-完整的.

结论:

• 新的算法为USO相位计算提供了相当大的效率增长.
• 这些发现突出了高效的相位操纵和简洁的USO表示的计算难度相位确定之间的二分法.
• 对USO阶段的结构性质进行进一步研究是有必要的.