Name
Title | ||
|---|---|---|
Optimality of Fast-Matching Algorithms for Random Networks With Applications to Structural Controllability. |
Abstract | ||
|---|---|---|
Network control refers to a very large and diverse set of problems including controllability of linear time-invariant dynamical systems, where the objective is to select an appropriate input to steer the network to a desired state. There are many notions of controllability, one of them being structural controllability , which is intimately connected to finding maximum matchings on the underlying network topology. In this work, we study fast, scalable algorithms for finding maximum matchings for a large class of random networks . First, we illustrate that degree distribution random networks are realistic models for real networks in terms of structural controllability. Subsequently, we analyze a popular, fast, and practical heuristic due to Karp and Sipser as well as a simplification of it. For both heuristics, we establish asymptotic optimality and provide results concerning the asymptotic size of maximum matchings for an extensive class of random networks. |
Year | Venue | Field |
|---|---|---|
2017 | IEEE Trans. Control of Network Systems | Discrete mathematics,Heuristic,Mathematical optimization,Combinatorics,Controllability,Network controllability,Network topology,Dynamical systems theory,Heuristics,Degree distribution,Network control,Mathematics |
DocType | Volume | Issue |
Journal | 4 | 4 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohamad Kazem Shirani Faradonbeh | 1 | 24 | 5.96 |
| Ambuj Tewari | 2 | 7 | 3.11 |
| George Michailidis | 3 | 7 | 3.45 |