Name
Abstract | ||
|---|---|---|
In this paper we consider decompositions of a positive dual-minor Boolean function f into f = f 1 f 2 ,…, f k , where all f j are positive and self-dual. It is shown that the minimum k having such a decomposition equals the chromatic number of a graph associated with f , and the problem of deciding whether a decomposition of size k exists is co-NP-hard, for k ⩾2. We also consider the canonical decomposition of f and show that the complexity of finding a canonical decomposition is equivalent to deciding whether two positive Boolean functions are mutually dual. Finally, for the class of path functions including the class of positive read-once functions, we show that the sizes of minimum decompositions and minimum canonical decompositions are equal, and present a polynomial total time algorithm to generate all minimal canonical decompositions. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0166-218X(99)00096-7 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
monotone boolean functions,read-once functions,path functions,positive boolean functions,coteries,positive dual-minor boolean function,minimum self-dual decomposition,decompositions of positive dual-minor functions,self-dual functions,games,boolean function,functional decomposition | Journal | 96-97 |
Issue | ISSN | Citations |
1 | Discrete Applied Mathematics | 5 |
PageRank | References | Authors |
0.53 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan C. Bioch | 1 | 217 | 40.62 |
| Toshihide Ibaraki | 2 | 2593 | 385.64 |
| Kazuhisa Makino | 3 | 1088 | 102.74 |