Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, August 6, 2014 - 4:24:56 PM
Last modification on : Wednesday, August 9, 2017 - 12:03:16 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 12:58:03 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Beate Bollig. On Symbolic Representations of Maximum Matchings and (Un)directed Graphs. 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. pp.286-300, ⟨10.1007/978-3-642-15240-5_21⟩. ⟨hal-01054452⟩



Record views


Files downloads