Iterative recovery of controllability via maximum matching

Shuo Zhang, Stephen Wolthusen

Research output: Contribution to conferencePaperpeer-review

77 Downloads (Pure)


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


  • Controllability Recovery
  • Dynamic Systems
  • Maximum Matching
  • Augmenting Path

Cite this