Triangle listing algorithms : back from the diversion

Ortmann, Mark; Brandes, Ulrik

Triangle listing algorithms : back from the diversion

Dateien

Ortmann_281153.pdfGröße: 928.96 KBDownloads: 2425

Datum

2014

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Informatik und Informationswissenschaft

Publikationstyp

Beitrag zu einem Konferenzband

Publikationsstatus

Published

Erschienen in

MCGEOCH, Catherine C., ed., Ulrich MEYER, ed.. 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014, pp. 1-8. ISBN 978-1-61197-319-8. Available under: doi: 10.1137/1.9781611973198.1

Zusammenfassung

We show that most algorithms from the literature on listing the triangles of a graph have a common abstraction. Our unifying framework highlights that these seemingly different algorithms are in fact instantiations of a single generic procedure, and even suggests some additional variants. More importantly, it yields parsimonious implementations that are in general more efficient than those described in the original works. In addition, we show that the running time of nearly every triangle listing variant is in O(a(G)m), where a(G) is the arboricity of the graph and m the number of edges. So far this bound has been proven only for Chiba and Nishizeki's (SIAM J. Computing, 1985) triangle listing algorithm. Finally, algorithmic experimentation reveals that an improved implementation of this algorithm outperforms all subsequently proposed algorithms.

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

ORTMANN, Mark, Ulrik BRANDES, 2014. Triangle listing algorithms : back from the diversion. In: MCGEOCH, Catherine C., ed., Ulrich MEYER, ed.. 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014, pp. 1-8. ISBN 978-1-61197-319-8. Available under: doi: 10.1137/1.9781611973198.1

BibTex

@inproceedings{Ortmann2014-05Trian-28115,
  year={2014},
  doi={10.1137/1.9781611973198.1},
  title={Triangle listing algorithms : back from the diversion},
  isbn={978-1-61197-319-8},
  publisher={Society for Industrial and Applied Mathematics},
  address={Philadelphia, PA},
  booktitle={2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX)},
  pages={1--8},
  editor={McGeoch, Catherine C. and Meyer, Ulrich},
  author={Ortmann, Mark and Brandes, Ulrik}
}

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/28115">
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/28115/1/Ortmann_281153.pdf"/>
    <dc:creator>Ortmann, Mark</dc:creator>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/28115/1/Ortmann_281153.pdf"/>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dc:language>eng</dc:language>
    <dcterms:title>Triangle listing algorithms : back from the diversion</dcterms:title>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:issued>2014-05</dcterms:issued>
    <dcterms:bibliographicCitation>2014 Proceedings of the sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) : January 5, 2014, Portland, Oregon, USA / Catherine C. McGeoch ... (eds.). - Philadelphia : Society for Industrial and Applied Mathematics, 2014. - S. 1-8. - ISBN 978-1-61197-319-8</dcterms:bibliographicCitation>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2014-06-13T12:51:38Z</dc:date>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:abstract xml:lang="eng">We show that most algorithms from the literature on listing the triangles of a graph have a common abstraction. Our unifying framework highlights that these seemingly different algorithms are in fact instantiations of a single generic procedure, and even suggests some additional variants. More importantly, it yields parsimonious implementations that are in general more efficient than those described in the original works. In addition, we show that the running time of nearly every triangle listing variant is in O(a(G)m), where a(G) is the arboricity of the graph and m the number of edges. So far this bound has been proven only for Chiba and Nishizeki's (SIAM J. Computing, 1985) triangle listing algorithm. Finally, algorithmic experimentation reveals that an improved implementation of this algorithm outperforms all subsequently proposed algorithms.</dcterms:abstract>
    <dc:contributor>Ortmann, Mark</dc:contributor>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/28115"/>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja