Bérczi, Kristóf and Boros, Endre and Cepek, Ondrej and Kucera, Petr and Makino, Kazuhisa (2021) Approximating minimum representations of key Horn functions. SIAM JOURNAL ON COMPUTING. ISSN 0097-5397 (print); 1095-7111 (online) (Submitted)
|
Text
1811.05160.pdf - Draft Version Download (308kB) | Preview |
|
|
Text
key_horn_minimization_revised_v2.pdf - Submitted Version Download (498kB) | Preview |
Abstract
Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem that remains hard even for the important subclass of key Horn functions. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all measures studied in the literature for which the problem is known to be hard.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Depositing User: | Kristóf Bérczi |
| Date Deposited: | 22 Sep 2019 04:24 |
| Last Modified: | 26 Sep 2021 05:38 |
| URI: | http://real.mtak.hu/id/eprint/100265 |
Actions (login required)
 |
Edit Item |
