IEICE TRANSACTIONS on Fundamentals
An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability
Summary :
We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in $2^{left(1 - Omega( rac{1}{log c}) ight)n}$ time for instances with n variables and cn nodes.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E99-A No.6 pp.1019-1024
- Publication Date
- 2016/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E99.A.1019
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Kazuhisa SETO
Seikei University
Junichi TERUYAMA
National Institute of Informatics,JST, ERATO
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuhisa SETO, Junichi TERUYAMA, "An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability" in IEICE TRANSACTIONS on Fundamentals,
vol. E99-A, no. 6, pp. 1019-1024, June 2016, doi: 10.1587/transfun.E99.A.1019.
Abstract: We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in $2^{left(1 - Omega( rac{1}{log c})
ight)n}$ time for instances with n variables and cn nodes.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E99.A.1019/_p
Copy
@ARTICLE{e99-a_6_1019,
author={Kazuhisa SETO, Junichi TERUYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability},
year={2016},
volume={E99-A},
number={6},
pages={1019-1024},
abstract={We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in $2^{left(1 - Omega( rac{1}{log c})
ight)n}$ time for instances with n variables and cn nodes.},
keywords={},
doi={10.1587/transfun.E99.A.1019},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - An Exact Algorithm for Oblivious Read-Twice Branching Program Satisfiability
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1019
EP - 1024
AU - Kazuhisa SETO
AU - Junichi TERUYAMA
PY - 2016
DO - 10.1587/transfun.E99.A.1019
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E99-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2016
AB - We propose an exact algorithm to determine the satisfiability of oblivious read-twice branching programs. Our algorithm runs in $2^{left(1 - Omega( rac{1}{log c})
ight)n}$ time for instances with n variables and cn nodes.
ER -
English
