JGraphT

Mentors: Student: Tymofii Chudakov

<p>This project is focused on developing an implementation of the Kolmogorov's Blossom V algorithm for minimum weight perfect matching, which is a known problem of combinatorial optimization. Adding this algorithm to the library will extend its support of matchings and make the next step towards implementing other algorithms requiring this one as a subroutine.<br> The project is divided into following parts:</p> <ul> <li>developing core part of the algorithm.</li> <li>developing fractional matching initialization for a significantly better running time in practice.</li> <li>writing benchmark tests, comparing the running time with other algorithms in the area.</li> <li>working on code optimizations and extensions of the algorithm.</li> </ul> <p>This project has 2 optional tasks: the price-and-repair technique for better running time on dense graphs, and a minimum cost flow algorithm, which in the context of this project can be used for optimal dual updates.</p>

Mentors: Student: Alexandru Valeanu

<p>JGraphT currently lacks proper support for trees (i.e. simple, undirected, connected, acyclic graphs). Sure, all algorithms that work on undirected graphs will work on trees but in some cases, there may be a much more efficient option. Also, there are some classic tree-algorithms that are currently missing from the library. I plan to work on the following:</p> <ul> <li>tree traversals</li> <li>algorithms for computing lowest common ancestors in trees and DAGs</li> <li>tree decompositions</li> <li>AHU algorithm for deciding tree isomorphism</li> <li>Prüfer encoding</li> </ul>