Name
Abstract | ||
|---|---|---|
We take a structural approach to the problem of designing the edge weights in an undirected graph subject to an upper bound on their total, so as to maximize the algebraic connectivity. Specifically, we first characterize the eigenvector(s) associated with the algebraic connectivity at the optimum, using optimization machinery together with eigenvalue sensitivity notions. Using these characterizations, we fully address optimal design in tree graphs that is quadratic in the number of vertices, and also obtain a suite of results concerning the topological and eigen-structure of optimal designs for bipartite and general graphs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/CDC.2008.4738734 | CDC |
Keywords | Field | DocType |
optimisation,bipartite graph,tree graph,algebraic connectivity,trees (mathematics),matrix algebra,i. introduction,topological structure,undirected graph optimal edge weight design,eigenvector,optimization machinery,eigenvalues and eigenfunctions,eigenvalue sensitivity notion,tree graphs,eigenvalues,search algorithm,upper bound,algorithm design and analysis,lower bound,optimal design,symmetric matrices,eigenvectors,graph theory,optimization,network design | Graph theory,Discrete mathematics,Mathematical optimization,Combinatorics,Tree (graph theory),Computer science,Bipartite graph,Graph Edge,Optimal design,Algebraic connectivity,Independent set,Connectivity | Conference |
ISSN | ISBN | Citations |
0191-2216 E-ISBN : 978-1-4244-3124-3 | 978-1-4244-3124-3 | 7 |
PageRank | References | Authors |
0.90 | 12 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yan Wan | 1 | 118 | 23.07 |
| Sandip Roy | 2 | 301 | 53.03 |
| Xu Wang | 3 | 62 | 8.73 |
| Ali Saberi | 4 | 499 | 83.21 |
| Tao Yang | 5 | 373 | 25.80 |
| Mengran Xue | 6 | 61 | 13.36 |
| Babak Malek | 7 | 7 | 0.90 |