• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Integer Programming and Combinatorial Optimization >A Combinatorial Algorithm for Computing the Degree of the Determinant of a Generic Partitioned Polynomial Matrix with 2 × 2 Submatrices
【24h】

A Combinatorial Algorithm for Computing the Degree of the Determinant of a Generic Partitioned Polynomial Matrix with 2 × 2 Submatrices

机译：一种组合算法，用于计算具有2×2个分布的通用分区多项式矩阵的决定因素的程度

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper, we consider the problem of computing the degree of the determinant of a block-structured symbolic matrix (a generic partitioned polynomial matrix) A = (A_(αβ)x_(αβ)t~(d_(αβ))), where A_(αβ) is a 2 × 2 matrix over a field F, x_(αβ) is an indeterminate, and d_(αβ) is an integer for α,β = 1,2,... ,n, and t is an additional indeterminate. This problem can be viewed as an algebraic generalization of the maximum perfect bipartite matching problem. The main result of this paper is a combinatorial O(n~5)-time algorithm for the deg-det computation of a (2 × 2)-type generic partitioned polynomial matrix of size 2n × 2n. We also present a min-max theorem between the degree of the determinant and a potential defined on vector spaces. Our results generalize the classical primal-dual algorithm (Hungarian method) and min-max formula (Egervary's theorem) for maximum weight perfect bipartite matching.
机译：在本文中，我们考虑计算块结构符号矩阵（通用分区多项式矩阵）a =（a_（αβ）x_（αβ）t〜（d_（αβ）））的确定的问题， 其中A_（αβ）在字段F上的2×2矩阵上，X_（αβ）是不确定的，并且D_（αβ）是α，β= 1,2，...，n和t的整数 额外的不确定。 该问题可以被视为最大完美二分匹配问题的代数概括。 本文的主要结果是用于DEG-DET计算的组合O（n〜5）-time算法（2×2）型通用尺寸2n×2n的多项式矩阵。 我们还在传染媒介空间上定义的决定因素的程度和潜在的最大最大定理。 我们的结果概括了经典的Primal-Dual算法（匈牙利方法）和MIN-MAX公式（EGERVARY的定理），以获得最大重量完美的双链匹配。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号