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 metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01054452
Contributor : Hal Ifip <>
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

File

03230286.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

448

Files downloads

330