摘要：We consider the sensitivity of algorithms for the maximum matching problem against edge and vertex modifications. When an algorithm A for the maximum matching problem is deterministic, the sensitivity of A on G is defined as max_{e â^^ E(G)} A(G) â-³ A(G - e) , where G-e is the graph obtained from G by removing an edge e â^^ E(G) and â-³ denotes the symmetric difference. When A is randomized, the sensitivity is defined as max_{e â^^ E(G)}d_{EM}(A(G),A(G-e)), where d_{EM}(â 2, there exists an algorithm that outputs a 1/(4α)-approximation to the maximum weighted matching in O(m log_α n) time, with normalized weighted sensitivity O(1).
关键词：Sensitivity analysis; maximum matching; graph algorithms
