MINING POSETS FROM LINEAR ORDERS

DOI10.1142/S1793830913500304zbMath1309.06002OpenAlexW1975173901MaRDI QIDQ2874042

Lenwood S. Heath, Michael Tan, Naren Ramakrishnan, Proceso Fernandez, 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

algorithmsposetspartial orderslinear extensions

Mathematics Subject Classification ID

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

Related Items (2)

Complexity reduction and approximation of multidomain systems of partially ordered data ⋮ A polynomial time algorithm for the 2-poset cover problem

Cites Work

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

This page was built for publication: MINING POSETS FROM LINEAR ORDERS