Name
Abstract | ||
|---|---|---|
Orthogonal forms of positive Boolean functions play an important role in reliability theory, since the probability that they take value 1 can be easily computed. However, few classes of disjunctive normal forms are known for which orthogonalization can be efficiently performed. An interesting class with this property is the class of shellable disjunctive normal forms (DNFs). In this paper, we present some new results about shellability. We establish that every positive Boolean function can be represented by a shellable DNF, we propose a polynomial procedure to compute the dual of a shellable DNF, and we prove that testing the so-called lexico-exchange (LE) property (a strengthening of shellability) is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1137/S089548019732180X | SIAM J. Discrete Math. |
Keywords | Field | DocType |
boolean normal forms,orthogonal dnfs,boolean functions,reliability,positive boolean function,disjunctive normal form,polynomial procedure,shellability,reliability computations,shellable dnf,important role,new result,reliability theory,interesting class,dualization,orthogonal form,shellable disjunctive normal form,normal form,boolean function | Graph theory,Boolean function,Discrete mathematics,Combinatorics,Polynomial,Disjunctive normal form,Cycle graph,Boolean algebra,Orthogonalization,Mathematics,Reliability theory | Journal |
Volume | Issue | ISSN |
13 | 2 | 0895-4801 |
Citations | PageRank | References |
5 | 0.51 | 11 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Endre Boros | 1 | 1779 | 155.63 |
| Yves Crama | 2 | 547 | 63.94 |
| Oya Ekin | 3 | 69 | 5.34 |
| Peter L. Hammer | 4 | 1996 | 288.93 |
| Toshihide Ibaraki | 5 | 2593 | 385.64 |
| Alexander Kogan | 6 | 5 | 0.51 |