Why do simple algorithms for triangle enumeration work in the real world?

DOI10.1145/2554797.2554819MaRDI QIDQ2988883zbMATH OpenOpenAlexFDO

Authors Jonathan W. Berry, Luke K. Fostvedt, Daniel J. Nordman, C. Seshadhri, Alyson G. Wilson, Cynthia Phillips

Publication date 19 May 2017

Published in Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2554797.2554819

zbMATH Keywords

expected analysisgraph algorithmsheavy-tailed degree distributiontriangle enumeration

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Why do simple algorithms for triangle enumeration work in the real world?
• An efficient algorithm for enumeration of triangulations
• Algorithmic determination of the enumerator for sums of three triangular numbers
• Enumerating trichromatic triangles containing the origin in linear time
• Efficiently enumerating minimal triangulations
• Triangle listing algorithms: back from the diversion
• Enumerating pseudo-triangulations in the plane

Cites work

• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(4)

• Sublinear time estimation of degree distribution moments: the arboricity connection
• Why do simple algorithms for triangle enumeration work in the real world?
• Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
• Counting triangles in power-law uniform random graphs

This page was built for publication: Why do simple algorithms for triangle enumeration work in the real world?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988883)