Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Implizite Algorithmen

Meine Implementierungen von OBDD-basierten impliziten Graphalgorithmen benutzen alle das CUDD BDD-Framework von Fabio Somenzi und ist hier zu finden. Eine Visual Studio Variante von CUDD 2.5.0 gibt es hier.

Implementierungen

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]

Veröffentlichungen

[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)