Name
Abstract | ||
|---|---|---|
A Boolean function is called (co-)connected if the subgraph of the Boolean hypercube induced by its (false) true points is connected; it is called strongly connected if it is both connected and co-connected. The concept of (co-)geodetic Boolean functions is defined in a similar way by requiring that at least one of the shortest paths connecting two (false) true points should consist only of (false) true points. This concept is further strengthened to that of convexity where every shortest path connecting two points of the same kind should consist of points of the same kind. This paper studies the relationships between these properties and the DNF representations of the associated Boolean functions. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0166-218X(99)00098-0 | Discrete Applied Mathematics |
Keywords | Field | DocType |
boolean function,geodetic,computational complexity,connectedness,boolean convexity,recognition,disjunctive normal form,monotone,unate,connected boolean function,shortest path | Boolean function,Discrete mathematics,Boolean circuit,Combinatorics,Parity function,Product term,Boolean expression,Complete Boolean algebra,Majority function,Two-element Boolean algebra,Mathematics | Journal |
Volume | Issue | ISSN |
96-97 | 1 | Discrete Applied Mathematics |
Citations | PageRank | References |
7 | 0.54 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Oya Ekin | 1 | 69 | 5.34 |
| Peter L. Hammer | 2 | 1996 | 288.93 |
| Alexander Kogan | 3 | 119 | 11.88 |