An efficient algorithm for batch stability testing

DOI10.1007/S00453-009-9320-5zbMath1209.68359OpenAlexW1994326691MaRDI QIDQ1959725

Brian C. Dean, John Dabney

Publication date: 7 October 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9320-5

zbMATH Keywords

stable matchingstable marriagedynamic connectivity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
• Near-optimal fully-dynamic graph connectivity
• Lower Bounds for the Stable Marriage Problem and Its Variants
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• An efficient algorithm for the “stable roommates” problem
• The Complexity of Counting Stable Marriages
• Sparsification—a technique for speeding up dynamic graph algorithms
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• College Admissions and the Stability of Marriage

This page was built for publication: An efficient algorithm for batch stability testing