An Improved KM Algorithm for Computing Structural Index of DAE System
An Improved KM Algorithm for Computing Structural Index of DAE System
复制标题
计算DAE系统结构指标的改进KM算法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Jianwen Cao
中科院分区：
文献类型：
--
作者：
Yan Zeng;Xuesong Wu;Jianwen Cao
提出了一种计算线性时不变微分代数方程(DAE)系统结构指数的改进KM算法。该问题在基于DAE系统结构指标和组合松弛理论的指标约简中具有实际意义。改进后的KM算法结合了贪婪思想和经典KM算法。它首先利用贪婪技术计算尽可能多的匹配点，然后在贪婪技术的过程中调用KM算法搜索匹配中不匹配的顶点。改进的KM算法将运行时间限制减少了一个系数r，即使用贪婪算法搜索的匹配数。一般情况下，时间复杂度为O(R2+(n-r)n2)，最优时间为O(N2)。
This paper proposes an improved KM algorithm to computing the structural index of linear time-invariant Differential Algebraic Equation (DAE) systems. The problem is of practical significance in index reduction based on structural index of DAE system and combinatorial relaxation theory. This improved KM algorithm combines greedy idea and classical KM algorithm. It first computes matches as much as possible using greedy technology, and then call KM algorithm to search the matches for the unmatched vertices during the step of greedy technology. The improved KM algorithm reduces the running time bound by a factor of r, the number of matches searched using greedy algorithm. Generally, the time complexity is O(r2+(n-r)n2), the optimal time is O(n2).