A Simple Analysis of Ranking in General Graphs
Abstract
We provide a simple combinatorial analysis of the Ranking algorithm, originally introduced in the seminal work by Karp, Vazirani, and Vazirani [KVV90], demonstrating that it achieves a \((1/2+c)\)-approximate matching for general graphs for \(c \ge 0.005\).
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Game Theory and Voting Systems
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 438–443
- Publication date
- 1 January 2026
- Language
- EN