Abstract
Controllability is significant for dynamical systems, and iterative recovery of controllability is indispensable sometimes. We consider any large, sparse ER random digraph with a linear time-invariant control model as an input graph, obtained by adding one node to an original random digraph, and we seek to recover its controllability via efficiently identifying a maximum matching of it rather than recomputation. Particularly, we assume that any input graph contains a known matching that is a maximum matching of the original random digraph. In our solution, we depend on a bipartite graph one-to-one mapped by an input digraph to find its augmenting paths relative to a matching corresponding to the known matching of the input graph. By finding augmenting paths within this mapped bipartite graph, we eventually find a maximum matching and recover the controllability of this input digraph in linear time as a result.
| Original language | English |
|---|---|
| Pages | 328-333 |
| Number of pages | 6 |
| DOIs | |
| Publication status | Published - 15 Jan 2018 |
| Event | 13th IEEE International Conference on Automation Science and Engineering - Wyndham Grand Xi'an South No. 208 Ci'en East Road Qujiang New District, Xi'an, China Duration: 20 Aug 2017 → 23 Aug 2017 Conference number: 40743 https://www.ieee.org/conferences_events/conferences/conferencedetails/index.html?Conf_ID=40743 |
Conference
| Conference | 13th IEEE International Conference on Automation Science and Engineering |
|---|---|
| Abbreviated title | CASE 2017 |
| Country/Territory | China |
| City | Xi'an |
| Period | 20/08/17 → 23/08/17 |
| Internet address |
Keywords
- Controllability Recovery
- Dynamic Systems
- Maximum Matching
- Augmenting Path