Triangle listing algorithms : back from the diversion

Zitieren

Dateien zu dieser Ressource

Prüfsumme: 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"> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:rights rdf:resource="http://nbn-resolving.org/urn:nbn:de:bsz:352-20140905103605204-4002607-1"/> <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"/> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/28115/1/Ortmann_281153.pdf"/> <dcterms:title>Triangle listing algorithms : back from the diversion</dcterms:title> <dc:creator>Brandes, Ulrik</dc:creator> <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> <dc:rights>deposit-license</dc:rights> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Ortmann, Mark</dc:creator> </rdf:Description> </rdf:RDF>

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

Ortmann_281153.pdf 93

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto