Maximum algebraic connectivity augmentation is NP-hard
From MaRDI portal
Publication:2517792
DOI10.1016/j.orl.2008.09.001zbMath1152.05343OpenAlexW2090718545MaRDI QIDQ2517792
Publication date: 9 January 2009
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2008.09.001
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40)
Related Items (14)
Augmenting the algebraic connectivity for certain families of graphs ⋮ The algebraic connectivity of graphs with given circumference ⋮ Algorithms for Finding Diameter-constrained Graphs with Maximum Algebraic Connectivity ⋮ Algorithms for synthesizing mechanical systems with maximal natural frequencies ⋮ Effects of adding arcs on the consensus convergence rate of leader-follower multi-agent systems ⋮ Unnamed Item ⋮ Heuristics for synthesizing robust networks with a diameter constraint ⋮ Optimizing network robustness by edge rewiring: a general framework ⋮ Experiments with two heuristic algorithms for the maximum algebraic connectivity augmentation problem ⋮ Note on von Neumann and Rényi entropies of a graph ⋮ Maximizing algebraic connectivity for certain families of graphs ⋮ On algebraic connectivity augmentation ⋮ Improving connectivity of compromised digital networks via algebraic connectivity maximisation ⋮ An approximation algorithm for the maximum spectral subgraph problem
Cites Work
This page was built for publication: Maximum algebraic connectivity augmentation is NP-hard