Time Complexity of Decentralized Fixed-Mode Verification
- Creators
- Lavaei, Javad
- Sojoudi, Somayeh
Abstract
Given an interconnected system, this note is concerned with the time complexity of verifying whether an unrepeated mode of the system is a decentralized fixed mode (DFM). It is shown that checking the decentralized fixedness of any distinct mode is tantamount to testing the strong connectivity of a digraph formed based on the system. It is subsequently proved that the time complexity of this decision problem using the proposed approach is the same as the complexity of matrix multiplication. This work concludes that the identification of distinct DFMs (by means of a deterministic algorithm, rather than a randomized one) is computationally very easy, although the existing algorithms for solving this problem would wrongly imply that it is cumbersome. This note provides not only a complexity analysis, but also an efficient algorithm for tackling the underlying problem.
Additional Information
© 2010 IEEE. Manuscript received September 18, 2008; revised March 24, 2009, and December 10, 2009. First published February 02, 2010; current version published April 02, 2010. This work was supported by the Office of Naval Research (ONR) MURI N00014-08-1-0747 "Scalable, Data-driven, and Provably-correct Analysis of Networks," ARO-MURI W911NF-08-1-0233 "Tools for the Analysis and Design of Complex Multi-Scale Networks," and the Army's W911NF-09-D-0001 Institute for Collaborative Biotechnology. Recommended by Associate Editor C. J. Tomlin.Attached Files
Published - Lavaei2010p9916Ieee_T_Automat_Contr.pdf
Files
Name | Size | Download all |
---|---|---|
md5:7c84d281fff520c49282f8c708219def
|
284.8 kB | Preview Download |
Additional details
- Eprint ID
- 18446
- Resolver ID
- CaltechAUTHORS:20100526-083621793
- N00014-08-1-0747
- Office of Naval Research (ONR)
- W911NF-08-1-0233
- Army Research Office (ARO)
- W911NF-09-D-0001
- Army Research Office (ARO)
- Created
-
2010-06-01Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field