Triangle listing algorithms : back from the diversion
| dc.contributor.author | Ortmann, Mark | |
| dc.contributor.author | Brandes, Ulrik | |
| dc.date.accessioned | 2014-06-13T12:51:38Z | deu |
| dc.date.issued | 2014-05 | |
| dc.description.abstract | 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. | eng |
| dc.description.version | published | |
| dc.embargo.terms | 2015-07-01 | deu |
| dc.identifier.citation | 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 | deu |
| dc.identifier.doi | 10.1137/1.9781611973198.1 | deu |
| dc.identifier.ppn | 407921427 | deu |
| dc.identifier.uri | http://kops.uni-konstanz.de/handle/123456789/28115 | |
| dc.language.iso | eng | deu |
| dc.legacy.dateIssued | 2014-06-13 | deu |
| dc.rights | terms-of-use | deu |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | deu |
| dc.subject.ddc | 004 | deu |
| dc.title | Triangle listing algorithms : back from the diversion | eng |
| dc.type | INPROCEEDINGS | deu |
| dspace.entity.type | Publication | |
| kops.citation.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}
} | |
| kops.citation.iso690 | 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 | deu |
| kops.citation.iso690 | 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 | eng |
| kops.citation.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> | |
| kops.description.openAccess | openaccessgreen | |
| kops.flag.knbibliography | true | |
| kops.identifier.nbn | urn:nbn:de:bsz:352-281153 | deu |
| kops.sourcefield | MCGEOCH, Catherine C., ed., Ulrich MEYER, ed.. <i>2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX)</i>. 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 | deu |
| kops.sourcefield.plain | 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 | deu |
| kops.sourcefield.plain | 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 | eng |
| kops.submitter.email | susanne.bohner@uni-konstanz.de | deu |
| relation.isAuthorOfPublication | a11caa0f-dd1c-4396-afc5-cf7b0dc74a00 | |
| relation.isAuthorOfPublication | fa1660c9-a071-4d01-9bdd-7adcd0e2d7d7 | |
| relation.isAuthorOfPublication.latestForDiscovery | a11caa0f-dd1c-4396-afc5-cf7b0dc74a00 | |
| source.bibliographicInfo.fromPage | 1 | |
| source.bibliographicInfo.toPage | 8 | |
| source.contributor.editor | McGeoch, Catherine C. | |
| source.contributor.editor | Meyer, Ulrich | |
| source.identifier.isbn | 978-1-61197-319-8 | |
| source.publisher | Society for Industrial and Applied Mathematics | |
| source.publisher.location | Philadelphia, PA | |
| source.title | 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) |
Dateien
Originalbündel
1 - 1 von 1
Vorschaubild nicht verfügbar
- Name:
- Ortmann_281153.pdf
- Größe:
- 928.96 KB
- Format:
- Adobe Portable Document Format
Lizenzbündel
1 - 1 von 1
Vorschaubild nicht verfügbar
- Name:
- license.txt
- Größe:
- 1.92 KB
- Format:
- Plain Text
- Beschreibung:
