Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets

DOI10.1016/j.ins.2019.05.079zbMath1453.06001OpenAlexW2948397046MaRDI QIDQ2224808

Julen Hurtado de Saracho, Irene Díaz, Elías F. Combarro

Publication date: 4 February 2021

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2019.05.079

zbMATH Keywords

posetMarkov chainsfuzzy measuresrandom generationlinear extension

Mathematics Subject Classification ID

Partial orders, general (06A06) Total orders (06A05) Computational methods for problems pertaining to ordered structures (06-08)

Related Items (6)

Knapsack problems with dependencies through non-additive measures and Choquet integral ⋮ Random generation of \(k\)-interactive capacities ⋮ Reduction of variables and constraints in fitting antibuoyant fuzzy measures to data using linear programming ⋮ Random generation of capacities and its application in comprehensive decision aiding ⋮ Aggregation with dependencies: capacities and fuzzy integrals ⋮ Random generation of linearly constrained fuzzy measures and domain coverage performance evaluation

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizing isometries on the order polytope with an application to the theory of fuzzy measures
• On the random generation and counting of weak order extensions of a poset with given class cardinalities
• Two poset polytopes
• On the conductance of order Markov chains
• Faster random generation of linear extensions
• Non-additive measure and integral
• Mixing times of lozenge tiling and card shuffling Markov chains
• Monotonicity-based consensus states for the monometric rationalisation of ranking rules and how they are affected by ties
• Monotonicity-based ranking on the basis of multiple partially specified reciprocal relations
• Combinatorial Markov chains on linear extensions
• Adjacency on the order polytope with applications to the theory of fuzzy measures
• Fast perfect sampling from linear extensions
• Markov chains on graded posets. Compatibility of up-directed and down-directed transition probabilities
• On random generation of fuzzy measures
• Theory of capacities
• Ordered Sets
• Optimal Partial-Order Plan Relaxation via MaxSAT
• Spectral Gap for Random-to-Random Shuffling on Linear Extensions
• The Computational Complexity of Estimating MCMC Convergence Time
• Topological sorting of large networks
• p-SYMMETRIC FUZZY MEASURES
• Scheduling with Precedence Constraints of Low Fractional Dimension
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets