Dimitrios Michail

Assoc. Prof/Research Scientist/Software Engineer

I have been writing software for almost 20 years, both open-source and proprietary software. My LinkedIn profile describes in more detail the various projects which I have participated in and the companies for which I have been consulting.

In this page I briefly describe my open source projects. If you use any of them in your research, I would appreciate it if you cite the corresponding publication. Citing software is just as important as citing any other important sources in your research. If you’re not sure whether or not to cite something, Shouldacite can help you decide if you should.

JGraphT

JGraphT is free production-grade Java library for graph-data structures and algorithms. The library is a big open-source project with a large number of contributors. I have been contributing to the library for more than 4 years and have also served as a Google Summer of Code Mentor in GSOC 2018.

JGraphT contains efficient graph data-structures and a very large collection of advanced graph algorithms. The following paper describes the internals of the library as well as the available algorithms:

  • D. Michail, J. Kinable, B. Naveh, and J. V. Sichi. JGraphT - A Java library for graph data structures and algorithms. ACM Transactions on Mathematical Software, 46(2), May 2020. web

I have also written Python bindings for JGraphT. For more information see the following:

JHeaps

JHeaps is a free, production-ready, efficient Java library containing a collection of heap data-structures. It contains an extensive collection of heap data structures such as:

  • tree-based addressable ones (Fibonacci, Pairing, Leftist, Skew, etc.)
  • double-ended mergeable and addressable heaps (reflected Fibonacci, reflected Pairing)
  • array-based (binary, D-ary, binary weak, etc.)
  • double-ended array-based (binary min-max)
  • monotone (addressable and non-addressable radix with double, long, int or BigInteger keys).

The project is available on Github.

I have also written Python bindings for JHeaps. For more information see the following:

Minimum Cycle Basis

This project implements algorithms to compute exact and approximate Minimum Cycle Bases of weighted graphs. For undirected graphs, four algorithms:

  • An \(O(m^3 + m n^2 \log n)\) time exact algorithm
  • An \(O( m^2 n^2 )\) time exact algorithm
  • An \(O( m^3 )\) time exact algorithm
  • An \(O( m n^{1+1/k} + min(m^3 + m n^2 \log n, n^{3+3/k}) )\) time \((2k-1)\)-approximate algorithm for any integer \(k >= 1\).

For directed graphs:

  • An \(O(m^3 + m n^2 \log n )\) exact Monte-Carlo algorithm
  • An \(O( n^{3+3/k} \log n )\) \((2k-1)\)-approximate Monte-Carlo algorithm
  • An \(O( m n^{1+1/k} + min(m^3 + m n^2 \log n, n^{3+3/k}) )\) time \((2k-1)\)-approximate Monte-Carlo algorithm for any integer \(k >= 1\)

If you use this package please consider citing the following paper:

  • K. Mehlhorn and D. Michail. Implementing Minimum Cycle Basis Algorithms. ACM Journal of Experimental Algorithmics, 11(2):1-14, 2006. pdf, web

The project is available on Github.

Parallel Minimum Cycle Basis

Newer library which implements algorithms to compute exact and approximate Minimum Cycle Bases of weighted graphs. The library is written in C++-14 using the Boost Graph libraries for the underlying graph implementation. It supports parallel and distributed execution using the TBB (Intel Threading Building Blocks) library and MPI.

If you use this package please consider citing the following paper:

  • K. Mehlhorn and D. Michail. Implementing Minimum Cycle Basis Algorithms. ACM Journal of Experimental Algorithmics, 11(2):1-14, 2006. pdf, web

The project is available on Github.

Matchings with One Sided Preferences

This library implements algorithms which compute different matchings in bipartite graphs with one sided preferences. At this point there are algorithms for two problems:

  • rank-maximal matchings
    The library implements an algorithm to compute a rank-maximal matching in a bipartite graph. The running time is \(O(C \sqrt{n} m)\). Here \(n\) is the number of vertices, \(m\) the number of edges and \(C\) the largest rank used on the optimal solution.

    As a second algorithm, a straight-forward implementation of a straight-forward reduction to the maximum weight matching is provided with running time \(O(n^2(m + n \log n))\) and space \(O(n^2)\).

  • popular matchings The library contains an algorithm to compute a popular matching in a bipartite graph. The running time is \(O(\sqrt{n} m)\) using linear space.

The project is available on Github.

Acknowledgement

Are you using any of the above software? Please cite the corresponding paper.

Trouble?

Having trouble when working with any of the above software packages? Send me an email!