Name | Download | Beschreibung | Benötigte Software | Veröffentlichung |
---|---|---|---|---|
Implizite Bipartite Matching Algorithmen | Version 0.1 (13.12.2012) | Implementierung von zwei impliziten Matching Algorithmen aus [1]. Beinhaltet auch den impliziten maximalen Matching Algorithmus aus [2]. Außerdem sind einige Generatoren für bipartite Graphen implementiert, z.B. für zufällige Rope-Graphen, Bäume, u.v.m. | CUDD 2.5.0 LEDA ab 6.3 (Website) |
[1] |
Impliziter Matching Algorithmus für Intervallgraphen | Version 0.1 (20.07.2015) | Implementierung der impliziten Algorithmen aus [3] inklusive zufälligen Intervallgraph-Generator. | CUDD 2.5.0 LEDA ab 6.3 (Website) |
[3] |
Randomisierte Implizite Algorithmen Implicit Algorithms | Version 0.1 (20.07.2015) Version 0.1 (20.07.2015) |
Implementierung des impliziten randomisierten maximalen Matching Algorithmus und des randomisierten Minimum Spanning Tree Algorithmus aus [4] inklusive Graphgenerator. | CUDD 2.5.0 LEDA ab 6.3 (Website) |
[4] |
[1] |
Beate Bollig, Marc Gillé und 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 und 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) |