Metatheorems for dynamic weighted matching
We consider the maximum weight matching (MWM) problem in dynamic graphs. We provide two reductions. The first reduces the dynamic MWM problem on m-edge, n-node graphs with weights bounded by N to the problem with weights bounded by (n/ϵ)2;), so that if the MWM problem can be α-Approximated with upda...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137773 |