Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Implicit Algorithms

My implementation of OBDD-based graph algorithms use the BDD-Framework CUDD by Fabio Somenzi which can be found here. A visual studio solution of CUDD 2.5.0 is provided here.

Implementation

Name Download Description Required Software Publication
Implicit Bipartite Matching Algorithms Version 0.1 (13.12.2012) Implementation of two implicit maximum matching algorithms from [1]. Consists also an implementation of the implicit maximal matching algorithm from [2]. Furthermore, a lot of generators for bipartite graphs were implemented, e.g., generating random rope graphs, trees, and much more. CUDD 2.5.0
LEDA 6.3 or higher (Website)		 [1]
Implicit Matching Algorithm for Interval Graphs Version 0.1 (20.07.2015) Implementation of the implicit matching algorithm from [3] with random (unit) interval graph generator. CUDD 2.5.0
LEDA 6.3 or higher (Website)		 [3]
Randomized Implicit Algorithms Version 0.1 (20.07.2015)
Version 0.1 (20.07.2015)		 Implementation of the implicit randomized maximal matching algorithm and randomized minimum spanning tree algorithm from [4] with random graph generator. CUDD 2.5.0
LEDA 6.3 or higher (Website)		 [4]

Publications

[1] Beate Bollig, Marc Gillé, and Tobias Pröger (2012):
Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations,
Proc. of TAMC 2012, Lecture Notes in Computer Science, Volume 7287, 473-486.
[2] Beate Bollig and Tobias Pröger (2012):
An efficient implicit OBDD-based algorithm for maximal matchings,
Proc. of LATA 2012, Lecture Notes in Computer Science, Volume 7183, 143-154.
[3] Marc Gillé (2013):
OBDD-Based Representation of Interval Graphs,
Proc. of WG 2013, Lecture Notes in Computer Science, Volume 8165, 286-297. (arXiv)
[4] Marc Bury (2015):
Randomized OBDD-Based Algorithms,
To appear in Proc. of SIROCCO 2015, Lecture Notes in Computer Science. (arXiv)