Maximum algebraic connectivity augmentation is NP-hard

DOI10.1016/j.orl.2008.09.001zbMath1152.05343OpenAlexW2090718545MaRDI QIDQ2517792

Damon Mosk-Aoyama

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

zbMATH Keywords

computational complexityalgebraic connectivity

Mathematics Subject Classification ID

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

• Transportation in graphs and the admittance spectrum
• Some simplified NP-complete graph problems
• Expander graphs and their applications
• Matrix Analysis
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum algebraic connectivity augmentation is NP-hard