Name
Abstract | ||
|---|---|---|
This note studies the learnability of ordered binary decision diagrams (obdds). We give a polynomial-time algorithm using membership and equivalence queries that finds the minimum obdd for the target respecting a given ordering. We also prove that both types of queries and the restriction to a given ordering are necessary if we want minimality in the output, unless P=NP. If learning has to occur with respect to the optimal variable ordering, polynomial-time learnability implies the approximability of two NP-hard optimization problems: the problem of finding the optimal variable ordering for a given obdd and the Optimal Linear Arrangement problem on graphs. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1007/3-540-60454-5_41 | ALT |
Keywords | DocType | ISBN |
learning ordered binary decision,polynomial time,optimization problem | Conference | 3-540-60454-5 |
Citations | PageRank | References |
19 | 0.74 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ricard Gavaldà | 1 | 1265 | 81.30 |
| David Guijarro | 2 | 33 | 2.22 |