Conference icon

Conference

Achieving new upper bounds for the hypergraph duality problem through logic

Abstract:

The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $\mathcal{G}$ and $\mathcal{H}$, decide whether $\mathcal{H}$ consists precisely of all minimal transversals of $\mathcal{G}$ (in which case we say that $\mathcal{G}$ is the dual of $\mathcal{H}$). This problem is equivalent to decide whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $\mathrm{GC}(\log^2 n,\mathrm{PTIME})$, where $\ma...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1145/2603088.2603103

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
European Commission More from this funder
European Social Fund More from this funder
Region of Calabria More from this funder
Publisher:
ACM Publisher's website
Pages:
43:1-43:1
Publication date:
2014
DOI:
URN:
uuid:944ffa92-e435-4cdc-8b6d-b9eea9f9331d
Source identifiers:
476102
Local pid:
pubs:476102
ISBN:
978-1-4503-2886-9

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP