Abstract
We introduce a new algorithmic technique that applies to several graph connectivity problems. Its power is demonstrated by experimental studies of the minimum-weight strongly-connected spanning subgraph problem and the minimum-weight augmentation problem. Even though we are unable to improve the approximation ratios for these problems, our studies indicate that the new method generates significantly better solutions than the current known approximation algorithms, and yields solutions very close to optimal. We believe that our technique will eventually lead to algorithms that improve the performance ratios as well.
| Original language | English (US) |
|---|---|
| State | Published - Jan 1 1999 |
| Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |
Other
| Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|---|
| City | Baltimore, MD, USA |
| Period | 1/17/99 → 1/19/99 |
ASJC Scopus subject areas
- Chemical Health and Safety
- Software
- Safety, Risk, Reliability and Quality
- Discrete Mathematics and Combinatorics