Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
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
CCS-Classification:G. Mathematics of Computing
Date of first Publication:2021/08/11
Series (Serial Number):ZIB-Report (21-25)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.