FISSION : A Practical Algorithm for Computing Minimum Balanced Node Separators

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2020
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen 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_55
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)
004 Informatik
Schlagwörter
Konferenz
14th Annual International Conference on Combinatorial Optimization and Application (COCOA 2020), 11. Dez. 2020 - 13. Dez. 2020, Dallas, TX, USA
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BLUM, 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_55
BibTex
@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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet