Title:  An Improved KM Algorithm for Computing Structural Index of DAE System 
Author:  Zeng, Yan
; Wu, Xuesong
; Cao, Jianwen

Conference Name:  12th International Symposium on Distributed Computing and Applications to Business, Engineering and Science (DCABES)

Conference Date:  SEP 0204, 2012

Issued Date:  2013

Conference Place:  London, ENGLAND

Keyword:  DAE
; Index Reduction
; Structural Index
; Bipartite Graph
; Greedy
; KM Algorithm

Publish Place:  IEEE

Indexed Type:  CPCI

ISBN:  9780769550602

Department:  [Zeng, Yan; Wu, Xuesong; Cao, Jianwen] Chinese Acad Sci, Inst Software, Lab Parallel Software & Computat Sci Software, Beijing 100190, Peoples R China.

Abstract:  This paper proposes an improved KM algorithm to computing the structural index of linear timeinvariant 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)). 
English Abstract:  This paper proposes an improved KM algorithm to computing the structural index of linear timeinvariant 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)). 
Language:  英语

Content Type:  会议论文

URI:  http://ir.iscas.ac.cn/handle/311060/16548

Appears in Collections:  软件所图书馆_会议论文

There are no files associated with this item.

Recommended Citation: 
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 0204, 2012.


