Optimality of Fast-Matching Algorithms for Random Networks With Applications to Structural Controllability
| Autor: | Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, George Michailidis |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
0209 industrial biotechnology
Mathematical optimization Control and Optimization Matching (graph theory) Dynamical systems theory Computer Networks and Communications Heuristic 0102 computer and information sciences 02 engineering and technology Degree distribution Network topology 01 natural sciences Controllability 020901 industrial engineering & automation 010201 computation theory & mathematics Control and Systems Engineering Signal Processing Algorithm design Heuristics |
| Zdroj: | IEEE Transactions on Control of Network Systems. 4:770-780 |
| ISSN: | 2325-5870 |
| DOI: | 10.1109/tcns.2016.2553366 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|