中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 会议论文
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 02-04, 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: 978-0-7695-5060-2
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 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)).
English Abstract: 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)).
Language: 英语
Content Type: 会议论文
URI: http://ir.iscas.ac.cn/handle/311060/16548
Appears in Collections:软件所图书馆_会议论文

Files in This Item:

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 02-04, 2012.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Zeng, Yan]'s Articles
[Wu, Xuesong]'s Articles
[Cao, Jianwen]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Zeng, Yan]‘s Articles
[Wu, Xuesong]‘s Articles
[Cao, Jianwen]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2020  中国科学院软件研究所 - Feedback
Powered by CSpace