Triangle listing algorithms : back from the diversion

Cite This

Files in this item

Checksum: MD5:96350737828b0025bdab39ef04a77587

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, pp. 1-8. ISBN 978-1-61197-319-8. Available under: doi: 10.1137/1.9781611973198.1

@inproceedings{Ortmann2014-05Trian-28115, title={Triangle listing algorithms : back from the diversion}, year={2014}, doi={10.1137/1.9781611973198.1}, isbn={978-1-61197-319-8}, address={Philadelphia, PA}, publisher={Society for Industrial and Applied Mathematics}, 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 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/28115"> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:contributor>Brandes, Ulrik</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <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> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/28115"/> <dc:rights>terms-of-use</dc:rights> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/28115/1/Ortmann_281153.pdf"/> <dc:creator>Brandes, Ulrik</dc:creator> <dcterms:title>Triangle listing algorithms : back from the diversion</dcterms:title> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/28115/1/Ortmann_281153.pdf"/> <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> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:issued>2014-05</dcterms:issued> <dc:language>eng</dc:language> <dc:contributor>Ortmann, Mark</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2014-06-13T12:51:38Z</dc:date> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Ortmann, Mark</dc:creator> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

Ortmann_281153.pdf 2145

This item appears in the following Collection(s)

Search KOPS


Browse

My Account