The search functionality is under construction.

Author Search Result

[Author] Nao KATOUGI(1hit)

1-1hit
  • Tree-Shellability of Restricted DNFs

    Yasuhiko TAKENAGA  Nao KATOUGI  

     
    PAPER-Algorithm Theory

      Vol:
    E91-D No:4
      Page(s):
    996-1002

    A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.