An efficient algorithm for batch stability testing

An efficient algorithm for batch stability testing

0.00 Avg rating0 Votes
Article ID: iaor20104951
Volume: 58
Issue: 1
Start Page Number: 52
End Page Number: 58
Publication Date: Sep 2010
Journal: Algorithmica
Authors: ,
Keywords: marriage problem
Abstract:

Given a stable marriage problem instance represented by a bipartite graph having 2n vertices and m edges, we describe an algorithm that can verify the stability of k different matchings in a batch fashion in O((m+kn)log2 n) time. This affirmatively answers a longstanding open question of Gusfield and Irving as to whether stability can be verified in a batch setting (after sufficient preprocessing) in time sub-quadratic in n.

Reviews

Required fields are marked *. Your email address will not be published.