zbMATH — the first resource for mathematics

Partial order with duality and consistent choice problem. (English) Zbl 0890.06002
The problem of consistent choice in a finite disjoint system of non-empty sets is considered. Any pair of chosen elements has to fulfill a given binary relation of consistency. The width of the system is the maximal cardinality of its members. The consistent choice problem is NP-complete for width \(>2\).
A connection between the consistent choice of width \(2\) and partially ordered sets with a unary operation of duality is described. Two \(O(n^2)\) algorithms for solving the consistent choice of width \(2\) are proposed on the base of the above connection. A condition is given under which the algorithms work also for width \(>2\).
06A06 Partial orders, general
68Q25 Analysis of algorithms and problem complexity
Full Text: EuDML
[1] COOK S. A.: The complexity of theorem proving procedures. Proc. 3rd ACM Sump. oii the Theoru of Computing, ACM, 1971, pp. 151-158. · Zbl 0253.68020
[2] GAVALEC M.: Computational complexity of consistent choice. Proc. 5th Conf. of EF TU, Math. Sect., KoŇ°ice, 1992, pp. 70-74.
[3] GAVALEC M.-HUDEC O.: Balanced location on a graph. Optimization 35 (1995), 367-372. · Zbl 0874.90114
[4] KNUTH D. E.-RAGHUNATHAN A.: The problem of compatible representatives. SIAM J. Discrete Math. 5 (1992), 422 427. · Zbl 0825.68494
[5] Algorithms and Complexity. Handbook of Theoretical Computer Science, rol. A (J. van Leeuven, Elsevier, Amsterdam, 1990. · Zbl 0925.68008
[6] TARJAN R. E.: Depth-first search and linear graph algorithm. SIAM J. Comput. 1 ( 1972). 146-160. · Zbl 0251.05107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.