Autark assignments of Horn CNFs

Kei Kimura; Kazuhisa Makino

doi:10.1007/s13160-017-0284-6

Autark assignments of Horn CNFs

Kei Kimura, Kazuhisa Makino

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	297-309
Number of pages	13
Journal	Japan Journal of Industrial and Applied Mathematics
Volume	35
Issue number	1
DOIs	https://doi.org/10.1007/s13160-017-0284-6
Publication status	Published - Mar 1 2018
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Engineering
Applied Mathematics

Access to Document

10.1007/s13160-017-0284-6

Cite this

@article{db400e60ed2e4e64afae8de3e196392a,

title = "Autark assignments of Horn CNFs",

abstract = "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.",

author = "Kei Kimura and Kazuhisa Makino",

note = "Publisher Copyright: {\textcopyright} 2017, The JJIAM Publishing Committee and Springer Japan KK, part of Springer Nature.",

year = "2018",

month = mar,

day = "1",

doi = "10.1007/s13160-017-0284-6",

language = "English",

volume = "35",

pages = "297--309",

journal = "Japan Journal of Industrial and Applied Mathematics",

issn = "0916-7005",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Autark assignments of Horn CNFs

AU - Kimura, Kei

AU - Makino, Kazuhisa

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 -

Autark assignments of Horn CNFs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this