Iterative recovery of controllability via maximum matching

Shuo Zhang; Stephen Wolthusen

doi:10.1109/COASE.2017.8256124

Iterative recovery of controllability via maximum matching

Shuo Zhang
, Stephen Wolthusen

Research output: Contribution to conference › Paper › peer-review

126 Downloads (Pure)

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	https://doi.org/10.1109/COASE.2017.8256124
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	https://www.ieee.org/conferences_events/conferences/conferencedetails/index.html?Conf_ID=40743

Keywords

Controllability Recovery
Dynamic Systems
Maximum Matching
Augmenting Path

Access to Document

10.1109/COASE.2017.8256124

Accepted ManuscriptAccepted author manuscript, 237 KB

Cite this

@conference{8043aab556414414aded71c49b3e382d,

title = "Iterative recovery of controllability via maximum matching",

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.",

keywords = "Controllability Recovery, Dynamic Systems, Maximum Matching, Augmenting Path",

author = "Shuo Zhang and Stephen Wolthusen",

year = "2018",

month = jan,

day = "15",

doi = "10.1109/COASE.2017.8256124",

language = "English",

pages = "328--333",

note = " 13th IEEE International Conference on Automation Science and Engineering, CASE 2017 ; Conference date: 20-08-2017 Through 23-08-2017",

url = "https://www.ieee.org/conferences\_events/conferences/conferencedetails/index.html?Conf\_ID=40743",

}

TY - CONF

T1 - Iterative recovery of controllability via maximum matching

AU - Zhang, Shuo

AU - Wolthusen, Stephen

N1 - Conference code: 40743

PY - 2018/1/15

Y1 - 2018/1/15

N2 - 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.

AB - 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.

KW - Controllability Recovery

KW - Dynamic Systems

KW - Maximum Matching

KW - Augmenting Path

U2 - 10.1109/COASE.2017.8256124

DO - 10.1109/COASE.2017.8256124

M3 - Paper

SP - 328

EP - 333

T2 - 13th IEEE International Conference on Automation Science and Engineering

Y2 - 20 August 2017 through 23 August 2017

ER -