An Efficient Algorithm for Partial Order Production

DOI10.1137/090759860zbMath1209.68272arXiv0811.2572OpenAlexW3098381999MaRDI QIDQ5390581

J. Ian Munro, Jean Cardinal, Raphaël M. Jungers, Gwenaël Joret, Samuel Fiorini

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.2572

zbMATH Keywords

partial ordergraph entropypartial order production problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Perfect graphs (05C17)

Related Items (5)

Sorting under partial information (without the ellipsoid algorithm). ⋮ Minimum entropy combinatorial optimization problems ⋮ Poset entropy versus number of linear extensions: the width-2 case. ⋮ Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50 ⋮ On Generalized Comparison-Based Sorting Problems

This page was built for publication: An Efficient Algorithm for Partial Order Production