English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We consider a graph parameter, the hydra number, arising from an optimization problem for Horn formulas in propositional logic. The hydra number of a graph G=(V,E) is the minimal number of hyperarcs of the form u, v→w required in a directed hypergraph H=(V,F), such that for every pair (u, v), the set of vertices reachable in H from {u, v} is the entire vertex set V if (u, v)∈E, and it is {u, v} otherwise. Here reachability is defined by the standard forward chaining or marking algorithm.  Various bounds are given for the hydra number. We show that the hydra number of a graph can be upper bounded by the number of edges plus the path cover number of its line graph, and this is a sharp bound for some graphs. On the other hand, we construct graphs with hydra number equal to the number of edges, but having arbitrarily large path cover number. Furthermore we characterize trees with low hydra number, give bounds for the hydra number of complete binary trees, discuss a related optimization problem and formulate several open problems.

Hydras: Directed Hypergraphs and Horn Formulas