一维逻辑阵布图的一个启发式算法

一维逻辑阵布图中列排序问题已被证明是一个ＮＰ（Ｎｏｎ—Ｐｏｌｙｎｏｍｉａｌ）－完全问题，本文提出一个新的启发式算法．算法的时间复杂度为Ｏ（ｒ·ｓ·｜Ｇ｜），其中｜Ｇ｜是逻辑阵的总门数，ｓ为单个线网连接的最多门数，ｒ为单门连接的最多线网数；其空间复杂度为Ｏ（｜Ｎ｜·｜Ｇ｜），其中｜Ｎ｜为线网总数．

关于生成有向图的全部有向回路的回路向量空间法

本文提出一个由有向图的(1)有向回路基集或(2)定向回路基集,通过线性组合,生成全部有向回路的算法。文中证明了一条“点数边数相等”原则。根据此原则,得到一个识别有向回路的简单方法,从而使算法的计算时间与对应的无向图算法基本相同。