An Improved KM Algorithm for Computing Structural Index of DAE System

摘要：

　　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,the number of matches searched using greedy algorithm.Generally,the time complexity is O(r2+(n-r)n2),the optimal time is O(n2).

关键词： DAE Index Reduction Structural Index Bipartite Graph Greedy KM Algorithm

作者: Yan Zeng Xuesong Wu Jianwen Cao

作者单位: Laboratory of Parallel Software and Computational Science of Software,Institute of Software Chinese Laboratory of Parallel Software and Computational Science of Software,Institute of Software Chinese

会议类型: 国际会议

会议名称: The 12th International Symposium on Distributed Computing and Applications to Business,Engineering and Science(DCABES 2013)(第十二届分布式计算及其应用国际学术研讨会)

会议地点: 英国伦敦

会议语种:英文

页码: 95-99

在线出版日期: 2013-09-02（万方平台首次上网日期，不代表论文的发表时间）