On Symbolic Representations of Maximum Matchings and (Un)directed Graphs

Abstract : The maximum matching problem is one of the most fundamental algorithmic graph problems and OBDDs are one of the most common dynamic data structures for Boolean functions. Since in some applications graphs become larger and larger, a research branch has emerged which is concerned with the theoretical design and analysis of so-called symbolic algorithms for classical graph problems on OBDD-represented graph instances. Typically problems get harder when their input is represented symbolically, nevertheless not many concrete non-trivial lower bounds are known. Here, it is shown that symbolic OBDD-based algorithms for the maximum matching problem need exponential space (with respect to the OBDD size of the input graph). Furthermore, it is shown that OBDD-representations for undirected graphs can be exponentially larger than OBDD-representations for their directed counterparts and vice versa.
Type de document :
Communication dans un congrès
Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.286-300, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_21〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054452
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:24:56
Dernière modification le : mercredi 9 août 2017 - 12:03:16
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 00:58:03

Fichier

03230286.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Beate Bollig. On Symbolic Representations of Maximum Matchings and (Un)directed Graphs. Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.286-300, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_21〉. 〈hal-01054452〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

125