On a class of totally unimodular matrices
On a class of totally unimodular matrices
复制标题
DOI：
10.1109/sfcs.1980.27
复制
发表时间：
1980-10
期刊：
影响因子：
--
通讯作者：
M. Yannakakis
中科院分区：
文献类型：
--
作者：
M. Yannakakis
我们研究一类矩阵，满足普通的充分条件，为全么模[C]，我们称之为限制全么模（RTUM）。我们证明了一个矩阵是RTUM当且仅当它可以以一种非常简单的方式分解成二分图或有向图的关联矩阵（或其转置），并给出了一个线性时间算法来执行这项任务。基于这种分解，我们证明了具有RTUM约束矩阵的0，1-规划问题具有与b-匹配和最大流问题相同的时间复杂度。
We examine the class of matrices that satisfy Commoner's sufficient condition for total unimodularity [C], which we call restricted totally unimodular (RTUM). We show that a matrix is RTUM if and only if it can be decomposed in a very simple way into the incidence matrices (or their transposes) of bipartite graphs or directed graphs, and give a linear time algorithm to perform this task. Based on this decomposition, we show that the 0,1 Integer Programming Problem with an RTUM matrix of constraints has the same time complexity as the b-matching and the max flow problems.