On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms

Autor: Etsuji Tomita, Alessio Conte

Publikováno v: Theoretical Computer Science. 899:1-24

We revisit the maximal clique enumeration algorithm cliques by Tomita et al. that appeared in Theoretical Computer Science in 2006. It is known to work in O ( 3 n / 3 ) -time in the worst-case for an n-vertex graph. This is worst-case optimal with re

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::18f2f149e4d6f42ff3251e8a5fc3f2e9
https://doi.org/10.1016/j.tcs.2021.11.005

Systematic categorization and evaluation of CbO-based algorithms in FCA

Autor: Jan Konecny, Petr Krajča

Publikováno v: Information Sciences. 575:265-288

Algorithms based on Close-by-One (CbO) are polynomial delay algorithms used for the enumeration of closed sets, particularly formal concepts in Formal Concept Analysis. We describe and categorize their distinctive features. We experimentally evaluate

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::34e57006c1775c5e118b8d206998f01c
https://doi.org/10.1016/j.ins.2021.06.024

Generating clause sequences of a CNF formula

Autor: Kristóf Bérczi, Khaled Elbassioni, Ondrej Cepek, Petr Kučera, Kazuhisa Makino, Endre Boros

Publikováno v: Theoretical Computer Science. 856:68-74

Given a CNF formula $\Phi$ with clauses $C_1,\ldots,C_m$ and variables $V=\{x_1,\ldots,x_n\}$, a truth assignment $a:V\rightarrow\{0,1\}$ of $\Phi$ leads to a clause sequence $\sigma_\Phi(a)=(C_1(a),\ldots,C_m(a))\in\{0,1\}^m$ where $C_i(a) = 1$ if c

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::abb9eec75785cde6c37554b21b93831d
https://doi.org/10.1016/j.tcs.2020.12.021

Geometric Amortization of Enumeration Algorithms

Autor: Capelli, Florent, Strozecki, Yann

Publikováno v: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), Mar 2023, Hamburg, Germany

In this paper, we introduce a technique we call geometric amortization for enumeration algorithms, which can be used to make the delay of enumeration algorithms more regular with little overhead on the space it uses. More precisely, we consider enume

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3a3aee03d3ad9669310f8ce81662154f

A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs

Autor: Khaled Elbassioni, Imran Rauf, Saurabh Ray

Publikováno v: Theoretical Computer Science. 767:26-33

We consider the problem of enumerating all minimal hitting sets of a given hypergraph ( V , R ) , where V is a finite set, called the vertex set and R is a set of subsets of V called the hyperedges. We show that, when the hypergraph admits a balanced

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::8e66905b9325862dd5fb03e6568987cd
https://doi.org/10.1016/j.tcs.2018.09.027