An Efficient Algorithm for Batch Stability Testing |
| |
Authors: | John Dabney Brian C Dean |
| |
Affiliation: | 1. School of Computing, Clemson University, Clemson, SC, USA
|
| |
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)log 2
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|