Finding Minimum Balanced Separators - an Exact Approach
Please always quote using this URN: urn:nbn:de:0297-zib-83138
- Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.
| Author: | Ralf BorndörferORCiD, Stephan SchwartzORCiD, William SurauORCiD |
|---|---|
| Document Type: | In Proceedings |
| Parent Title (English): | Operations Research Proceedings 2021 |
| First Page: | 154 |
| Last Page: | 159 |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING |
| CCS-Classification: | G. Mathematics of Computing |
| Date of first Publication: | 2021/08/11 |
| Series (Serial Number): | ZIB-Report (21-25) |
| ISSN: | 1438-0064 |
| DOI: | https://doi.org/https://doi.org/10.1007/978-3-031-08623-6_24 |
