scientific article; zbMATH DE number 1154176

MaRDI QIDQ4389705zbMATH OpenFDO

Authors M. Gavalec

Publication date 18 May 1998

Full work available at URL https://eudml.org/doc/34438

zbMATH Keywords

consistent choice problemNP-completenesspartial orderpolynomial algorithm

Mathematics Subject Classification ID

Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25)

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 3855106
• Algorithms for dualization over products of partially ordered sets
• Complexity of representation-of-choice functions as compositions. Asymptotic estimates of complexity characteristics
• scientific article; zbMATH DE number 4200270
• SOME ORDER DUALITIES IN LOGIC, GAMES AND CHOICES

Cites work

• Balanced location on a graph
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 53529 (Why is no real title available?)
• The complexity of theorem-proving procedures
• The Problem of Compatible Representatives

Cited in

(2)

• scientific article; zbMATH DE number 3855106 (Why is no real title available?)
• SOME ORDER DUALITIES IN LOGIC, GAMES AND CHOICES

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4389705)