On Engineering Dynamic Graph Algorithms
summary
Implements two families of dynamic solutions for weighted k-edge-coloring: a randomized dyn-greedy and a modified Misra–Gries-based dyn-kEC, plus a batch 2-approx algorithm (batch-2apx), filtering and hybrid heuristics; proves batch-2apx is 1/2-approx and shows dyn methods cut recourse drastically. Empirical study on 30 pfabric traces (thousands of nodes, batches up to 66.4k) and synthetic graphs finds dynamic methods beat static kEC when fraction phi of changed edges ≤0.1, hybrids help for large batches, and post-processing recovers quality lost to filtering.
AI-written summary · about