Mining posets from linear orders.

DOI10.1142/S1793830913500304MaRDI QIDQ2874042zbMATH OpenOpenAlexFDO

Authors Proceso L. Fernandez, Lenwood S. Heath, Naren Ramakrishnan, Michael Tan, John Paul C. Vergara

Publication date 28 January 2014

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830913500304

zbMATH Keywords

algorithmslinear extensionspartial ordersposets

Mathematics Subject Classification ID

Total orders (06A05) Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)

Recommendations

• Generating Linear Extensions Fast
• Generating the Linear Extensions of Certain Posets by Transpositions
• Computing linear extensions for polynomial posets subject to algebraic constraints
• Sorting and selection in posets
• Sorting and selection in posets

Cites work

• A loop-free algorithm for generating the linear extensions of a poset
• Counting linear extensions
• Generating Linear Extensions Fast
• Generating linear extensions of posets by transpositions
• Generating the Linear Extensions of Certain Posets by Transpositions
• Introduction to algorithms
• Loopless generation of linear extensions of a poset
• Some simplified NP-complete graph problems
• The average number of linear extensions of a partial order
• The Complexity of the Partial Order Dimension Problem
• The general maximum matching algorithm of Micali and Vazirani
• The Hardness of Approximating Poset Dimension

Cited in

(3)

• A polynomial time algorithm for the 2-poset cover problem
• Complexity reduction and approximation of multidomain systems of partially ordered data
• Computing linear extensions for polynomial posets subject to algebraic constraints

This page was built for publication: Mining posets from linear orders.

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