Publikation:

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

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

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. Lecture Notes in Computer Science. 12577. 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

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

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. Lecture Notes in Computer Science. 12577. 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
Diese Publikation teilen