Open AccessAn Efficient Algorithm for Batch Stability Testing
Author(s) -
John Dabney,
Brian C. Dean
Publication year - 2009
Publication title -
algorithmica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.647
H-Index - 78
eISSN - 1432-0541
pISSN - 0178-4617
DOI - 10.1007/s00453-009-9320-5
Subject(s) - bipartite graph , theory of computation , stability (learning theory) , preprocessor , combinatorics , stable marriage problem , mathematics , algorithm , graph , quadratic equation , discrete mathematics , computer science , matching (statistics) , artificial intelligence , statistics , geometry , machine learning
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom