An Improved KM Algorithm for Computing Structural Index of DAE System
文献类型：会议论文
| 作者 | Zeng, Yan ; Wu, Xuesong ; Cao, Jianwen |
| 出版日期 | 2013 |
| 会议名称 | 12th International Symposium on Distributed Computing and Applications to Business, Engineering and Science (DCABES) |
| 会议日期 | SEP 02-04, 2012 |
| 会议地点 | London, ENGLAND |
| 关键词 | DAE Index Reduction Structural Index Bipartite Graph Greedy KM Algorithm |
| 页码 | 95-99 |
| 中文摘要 | 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(r(2) + (n - r)n(2)), the optimal time is O(n(2)). |
| 英文摘要 | 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(r(2) + (n - r)n(2)), the optimal time is O(n(2)). |
| 收录类别 | CPCI |
| 会议录出版地 | IEEE |
| 语种 | 英语 |
| ISBN号 | 978-0-7695-5060-2 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/16548]  |
| 专题 | 软件研究所_软件所图书馆_会议论文 |
| 推荐引用方式 GB/T 7714 | Zeng, Yan,Wu, Xuesong,Cao, Jianwen. An Improved KM Algorithm for Computing Structural Index of DAE System[C]. 见:12th International Symposium on Distributed Computing and Applications to Business, Engineering and Science (DCABES). London, ENGLAND. SEP 02-04, 2012. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。