A Julia/JuMP Package for Maximizing Algebraic Connectivity of Undirected Weighted Graphs
Author harshangrjn
4 Stars
Updated Last
1 Year Ago
Started In
April 2021

Status: CI Documentation codecov


LaplacianOpt.jl is a Julia package which implements polyhedral relaxation-based algorithms for optimization of weighted graph Laplacians. Given a complete weighted, undirected graph, this package provides an optimal (and if preferable, an approximate) spanning tree which has the maximum second smallest eigenvalue of the graph Laplacian, also known as the Algebraic Connectivity of the graph. This package also implements various types of convex relaxations to the Laplacian optimization problem.


  • Clone the repository.
  • Open a terminal in the repo folder and run julia --project=..
  • Hit ] to open the project environment and run test to run unit tests. If you see an error because of missing packages, run resolve.

Check the "examples" folder on how to use this package.

Bug reports and support

Please report any issues via the Github issue tracker. All types of issues are welcome and encouraged; this includes bug reports, documentation typos, feature requests, etc.


This work was supported by Los Alamos National Laboratory's LDRD Early Career Research Award, "20190590ECR: Discrete Optimization Algorithms for Provable Optimal Quantum Circuit Design". The primary developer of this package is Harsha Nagarajan (@harshangrjn).


If you find LaplacianOpt.jl useful in your work, we request you to cite the following paper [link]:

  title={On maximizing algebraic connectivity of networks for various engineering applications},
  author={Nagarajan, Harsha and Rathinam, Sivakumar and Darbha, Swaroop},
  booktitle={European Control Conference (ECC)},

Used By Packages

No packages found.