Finding a Level Ideal of a Poset

DOI10.1007/978-3-642-02882-3_32MaRDI QIDQ5323080zbMATH OpenOpenAlexFDO

Authors Shuji Kijima, Toshio Nemoto

Publication date 23 July 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02882-3_32

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Matching models (91B68)

Recommendations

• On randomized approximation for finding a level ideal of a poset and the generalized median stable matchings
• The Generalized Median Stable Matchings: Finding Them Is Not That Easy
• The Complexity of Counting Stable Marriages
• On estimating the number of order ideals in partial orders, with some applications
• Optimal matchings in posets

Cites work

• An algorithm to generate the ideals of a partial order
• College Admissions and the Stability of Marriage
• Every finite distributive lattice is a set of stable matchings
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• scientific article; zbMATH DE number 5764911 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 48303 (Why is no real title available?)
• scientific article; zbMATH DE number 1354145 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• Many-to-One Stable Matching: Geometry and Fairness
• Median stable matching for college admissions
• On the complexity of dynamic programming for sequencing problems with precedence constraints
• Smith and Rawls share a room: stability and medians
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Counting Stable Marriages
• The Generalized Median Stable Matchings: Finding Them Is Not That Easy
• The geometry of fractional stable matchings and its applications

Cited in

(2)

• On randomized approximation for finding a level ideal of a poset and the generalized median stable matchings
• Sex-equal stable matchings: complexity and exact algorithms

This page was built for publication: Finding a Level Ideal of a Poset

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