A Simple Analysis of Ranking in General Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914152768864256 |
|---|---|
| author | Derakhshan, Mahsa Roghani, Mohammad Saneian, Mohammad Yu, Tao |
| author_facet | Derakhshan, Mahsa Roghani, Mohammad Saneian, Mohammad Yu, Tao |
| contents | 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 \geq 0.005$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_08801 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Simple Analysis of Ranking in General Graphs Derakhshan, Mahsa Roghani, Mohammad Saneian, Mohammad Yu, Tao Data Structures and Algorithms 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 \geq 0.005$. |
| title | A Simple Analysis of Ranking in General Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.08801 |