An Efficient Implicit OBDD-Based Algorithm for Maximal Matchings

Autor:	Tobias Pröger, Beate Bollig
Rok vydání:	2012
Předmět:	Combinatorics Discrete mathematics Optimization problem Deterministic finite automaton Matching (graph theory) Maximum flow problem Maximal independent set Boolean function Data structure Boolean data type Algorithm MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Language and Automata Theory and Applications ISBN: 9783642283314 LATA
DOI:	10.1007/978-3-642-28332-1_13
Popis:	The maximal matching problem, i.e., the computation of a matching that is not a proper subset of another matching, is a fundamental optimization problem and algorithms for maximal matchings have been used as submodules for problems like maximal node-disjoint paths or maximum flow. Since in some applications graphs become larger and larger, a research branch has emerged which is concerned with the design and analysis of implicit algorithms for classical graph problems. Input graphs are given as characteristic Boolean functions of their edge sets and problems have to be solved by functional operations. As OBDDs, which are closely related to deterministic finite automata, are a well-known data structure for Boolean functions, OBDD-based algorithms are used as a heuristic approach to handle very large graphs. Here, an implicit OBDD-based maximal matching algorithm is presented that uses only a polylogarithmic number of functional operations with respect to the number of vertices of the input graph.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::aa1b7fadc9ab1231b1e85e567656341e https://doi.org/10.1007/978-3-642-28332-1_13 Zobrazit plný text záznamu