An Improved KM Algorithm for Computing Structural Index of DAE System

ISCAS OpenIR

	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)
页码	95-99
会议日期	SEP 02-04, 2012
会议地点	London, ENGLAND
收录类别	CPCI
出版地	IEEE
ISBN	978-0-7695-5060-2
部门归属	[Zeng, Yan; Wu, Xuesong; Cao, Jianwen] Chinese Acad Sci, Inst Software, Lab Parallel Software & Computat Sci Software, Beijing 100190, Peoples R China.
摘要	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)).
关键词	Dae Index Reduction Structural Index Bipartite Graph Greedy Km Algorithm
语种	英语
内容类型	会议论文
URI标识	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]. IEEE,2013:95-99.