Iterative recovery of controllability via maximum matching. / Zhang, Shuo; Wolthusen, Stephen.

2018. 328-333 Paper presented at 13th IEEE International Conference on Automation Science and Engineering, Xi'an, China.

Research output: Contribution to conferencePaper




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 languageEnglish
Number of pages6
Publication statusPublished - 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 201723 Aug 2017
Conference number: 40743


Conference 13th IEEE International Conference on Automation Science and Engineering
Abbreviated titleCASE 2017
Internet address
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28815420