FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Projekt
Open Access-Veröffentlichung
Sammlungen
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
Given an undirected graph, a balanced node separator is a set of nodes whose removal splits the graph into connected components of limited size. Balanced node separators are used for graph partitioning, for the construction of graph data structures, and for measuring network reliability. It is NP-hard to decide whether a graph has a balanced node separator of size at most k. Therefore, practical algorithms typically try to find small separators in a heuristic fashion. In this paper, we present a branching algorithm that for a given value k either outputs a balanced node separator of size at most k or certifies that k is a valid lower bound. Using this algorithm iteratively for growing values of k allows us to find a minimum balanced node separator. To make this algorithm scalable to real-world (road) networks of considerable size, we first describe pruning rules to reduce the graph size without affecting the minimum balanced separator size. In addition, we prove several structural properties of minimum balanced node separators which are then used to reduce the branching factor and search depth of our algorithm. We experimentally demonstrate the applicability of our algorithm to graphs with thousands of nodes and edges. Finally, we showcase the usefulness of having minimum balanced separators for judging the quality of existing heuristics, for improving preprocessing-based route planning techniques on road networks, and for lower bounding important graph parameters.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BLUM, Johannes, Ruoying LI, Sabine STORANDT, 2020. FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators. 14th Annual International Conference on Combinatorial Optimization and Application (COCOA 2020). Dallas, TX, USA, 11. Dez. 2020 - 13. Dez. 2020. In: WU, Weili, ed., Zhongnan ZHANG, ed.. Combinatorial Optimization and Applications : 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11-13, 2020, proceedings. Cham: Springer, 2020, pp. 817-832. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-030-64842-8. Available under: doi: 10.1007/978-3-030-64843-5_55BibTex
@inproceedings{Blum2020FISSI-52198, year={2020}, doi={10.1007/978-3-030-64843-5_55}, title={FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators}, number={12577}, isbn={978-3-030-64842-8}, issn={0302-9743}, publisher={Springer}, address={Cham}, series={Lecture Notes in Computer Science}, booktitle={Combinatorial Optimization and Applications : 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11-13, 2020, proceedings}, pages={817--832}, editor={Wu, Weili and Zhang, Zhongnan}, author={Blum, Johannes and Li, Ruoying and Storandt, Sabine} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52198"> <dcterms:title>FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators</dcterms:title> <dc:creator>Storandt, Sabine</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:rights>terms-of-use</dc:rights> <dcterms:abstract xml:lang="eng">Given an undirected graph, a balanced node separator is a set of nodes whose removal splits the graph into connected components of limited size. Balanced node separators are used for graph partitioning, for the construction of graph data structures, and for measuring network reliability. It is NP-hard to decide whether a graph has a balanced node separator of size at most k. Therefore, practical algorithms typically try to find small separators in a heuristic fashion. In this paper, we present a branching algorithm that for a given value k either outputs a balanced node separator of size at most k or certifies that k is a valid lower bound. Using this algorithm iteratively for growing values of k allows us to find a minimum balanced node separator. To make this algorithm scalable to real-world (road) networks of considerable size, we first describe pruning rules to reduce the graph size without affecting the minimum balanced separator size. In addition, we prove several structural properties of minimum balanced node separators which are then used to reduce the branching factor and search depth of our algorithm. We experimentally demonstrate the applicability of our algorithm to graphs with thousands of nodes and edges. Finally, we showcase the usefulness of having minimum balanced separators for judging the quality of existing heuristics, for improving preprocessing-based route planning techniques on road networks, and for lower bounding important graph parameters.</dcterms:abstract> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-12-21T10:48:13Z</dcterms:available> <dc:contributor>Li, Ruoying</dc:contributor> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/52198"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:issued>2020</dcterms:issued> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:language>eng</dc:language> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-12-21T10:48:13Z</dc:date> <dc:creator>Li, Ruoying</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Blum, Johannes</dc:contributor> <dc:contributor>Storandt, Sabine</dc:contributor> <dc:creator>Blum, Johannes</dc:creator> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> </rdf:Description> </rdf:RDF>