Maximum algebraic connectivity augmentation is NP-hard

DOI10.1016/J.ORL.2008.09.001MaRDI QIDQ2517792zbMATH OpenOpenAlexFDO

Authors 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

algebraic connectivitycomputational complexity

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Experiments with two heuristic algorithms for the maximum algebraic connectivity augmentation problem
• Graph-Theoretic Concepts in Computer Science
• A minimum 3-connectivity augmentation of a graph
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

Cites work

• Expander graphs and their applications
• scientific article; zbMATH DE number 1944141 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• Matrix Analysis
• Some simplified NP-complete graph problems
• Transportation in graphs and the admittance spectrum

Cited in

(22)

• Augmenting the algebraic connectivity for certain families of graphs
• Heuristics for synthesizing robust networks with a diameter constraint
• Optimizing network robustness by edge rewiring: a general framework
• Algorithms for synthesizing mechanical systems with maximal natural frequencies
• Improving connectivity of compromised digital networks via algebraic connectivity maximisation
• An approximation algorithm for the maximum spectral subgraph problem
• Maximizing algebraic connectivity for certain families of graphs
• The algebraic connectivity of graphs with given circumference
• Experiments with two heuristic algorithms for the maximum algebraic connectivity augmentation problem
• Note on von Neumann and Rényi entropies of a graph
• Algorithms for finding diameter-constrained graphs with maximum algebraic connectivity
• On algebraic connectivity augmentation
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• Effects of adding arcs on the consensus convergence rate of leader-follower multi-agent systems
• Minimizing the effective graph resistance by adding links is NP-hard
• Effects on the algebraic connectivity of weighted graphs under edge rotations
• Attainable bounds for algebraic connectivity and maximally connected regular graphs
• The consensus performance of leader-follower multi-agent systems under reversing the directions of arcs
• Interaction topology optimization by adjustment of edge weights to improve the consensus convergence and prolong the sampling period for a multi-agent system
• The role of arc rotation on improving consensus convergence rate for a leader-follower multi-agent system
• On the non-submodularity of the problem of adding links to minimize the effective graph resistance
• Improving consensus convergence rate and increasing sample period for sampled-data consensus of multi-agent systems based on rewiring

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2517792)