KOPS - The Institutional Repository of the University of Konstanz

FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators

FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

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, Dec 11, 2020 - Dec 13, 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, 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_55

@inproceedings{Blum2020FISSI-52198, title={FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators}, year={2020}, doi={10.1007/978-3-030-64843-5_55}, number={12577}, isbn={978-3-030-64842-8}, issn={0302-9743}, address={Cham}, publisher={Springer}, 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 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/rdf/resource/123456789/52198"> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:language>eng</dc:language> <dcterms:title>FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators</dcterms:title> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <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> <dc:creator>Blum, Johannes</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/52198"/> <dc:contributor>Blum, Johannes</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Storandt, Sabine</dc:creator> <dc:contributor>Storandt, Sabine</dc:contributor> <dc:contributor>Li, Ruoying</dc:contributor> <dc:creator>Li, Ruoying</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-12-21T10:48:13Z</dcterms:available> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-12-21T10:48:13Z</dc:date> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:issued>2020</dcterms:issued> <dc:rights>terms-of-use</dc:rights> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account