TY - JOUR
T1 - Autark assignments of Horn CNFs
AU - Kimura, Kei
AU - Makino, Kazuhisa
N1 - Publisher Copyright:
© 2017, The JJIAM Publishing Committee and Springer Japan KK, part of Springer Nature.
PY - 2018/3/1
Y1 - 2018/3/1
N2 - In this paper, we consider autark and linear autark assignments of Horn CNFs. We first study maximal autark assignments of Horn CNFs and devise a linear time algorithm of computing these assignments. This complements the previous work by Marek which reveals the properties of minimal autark assignments of Horn CNFs. We then consider linear autark assignments of Horn CNFs and give a combinatorial characterization of the existence of such an assignment. By making use of this characterization, we devise a linear time algorithm of finding linear autark assignments of Horn CNFs.
AB - In this paper, we consider autark and linear autark assignments of Horn CNFs. We first study maximal autark assignments of Horn CNFs and devise a linear time algorithm of computing these assignments. This complements the previous work by Marek which reveals the properties of minimal autark assignments of Horn CNFs. We then consider linear autark assignments of Horn CNFs and give a combinatorial characterization of the existence of such an assignment. By making use of this characterization, we devise a linear time algorithm of finding linear autark assignments of Horn CNFs.
UR - http://www.scopus.com/inward/record.url?scp=85038639004&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85038639004&partnerID=8YFLogxK
U2 - 10.1007/s13160-017-0284-6
DO - 10.1007/s13160-017-0284-6
M3 - Article
AN - SCOPUS:85038639004
SN - 0916-7005
VL - 35
SP - 297
EP - 309
JO - Japan Journal of Industrial and Applied Mathematics
JF - Japan Journal of Industrial and Applied Mathematics
IS - 1
ER -