Algorithms for dualization over products of partially ordered sets

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

Let P = P1 × ⋯ × Pn be the product of n partially ordered sets (posets). Given a subset A ⊆ P, we consider problem DUAL(P, A, B) of extending a given partial list B of maximal independent elements of A in P. We give quasi-polynomial time algorithms for solving problem DUAL(P, A, B) when each poset Pi belongs to one of the following classes: (i) semilattices of bounded width, (ii) forests, that is, posets with acyclic underlying graphs, with either bounded in-degrees or out-degrees, or (iii) lattices defined by a set of real closed intervals.

Original languageBritish English
Pages (from-to)487-510
Number of pages24
JournalSIAM Journal on Discrete Mathematics
Volume23
Issue number1
DOIs
StatePublished - 2008

Keywords

  • Duality testing
  • Enumeration algorithms
  • Forests
  • Hypergraph transversals
  • Infrequent elements
  • Lattices
  • Monotone generation
  • Monotone properties
  • Ordered sets

Fingerprint

Dive into the research topics of 'Algorithms for dualization over products of partially ordered sets'. Together they form a unique fingerprint.

Cite this