ALGORITHMS FOR DUALIZATION OVER PRODUCTS OF PARTIALLY ORDERED SETS

摘要

Let P = P_1 × ... × P_n be the product of n partially ordered sets (posets). Given a subset A is contained in 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 P_i belongs to one of the following classes: (ⅰ) semilattices of bounded width, (ⅱ) forests, that is, posets with acyclic underlying graphs, with either bounded in-degrees or out-degrees, or (ⅲ) lattices defined by a set of real closed intervals.