ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Alles auswählen Exportieren

Unbekannt

Finding Minimum Balanced Separators - an Exact Approach (2021)

Borndörfer, Ralf ; Schwartz, Stephan ; Surau, William

zur Merkliste hinzufügen auf der Merkliste

Details

Publikationsdatum: 2022-08-31

Beschreibung: 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.

Sprache: Englisch

Materialart: conferenceobject , doc-type:conferenceObject

Format: application/pdf

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

OPUS

PDF

Überblick

Treffer 1 - 1 | 1 Treffer