Listing triangles

DOI10.1007/978-3-662-43948-7_19MaRDI QIDQ5167744zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andreas Björklund, Rasmus Pagh, Uri Zwick, Virginia Vassilevska Williams

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-43948-7_19

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Triangle listing algorithms: back from the diversion
• Experimental and Efficient Algorithms
• Main-memory triangle computations for very large (sparse (power-law)) graphs

Cited in

(35)

• It's all a matter of degree. Using degree information to optimize multiway joins
• iTri: index-based triangle listing in massive graphs
• An efficient exact algorithm for triangle listing in large graphs
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• A comparative study of dictionary matching with gaps: limitations, techniques and challenges
• Finding the largest triangle in a graph in expected quadratic time
• Summarized bit batch-based triangle listing in massive graphs
• Online recognition of dictionary with one gap
• Fooling views: a new lower bound technique for distributed computations under congestion
• Mind the gap!
• 3SUM, 3XOR, triangles
• Clique counting in MapReduce: algorithms and experiments
• Dynamic set intersection
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Approximately counting triangles in sublinear time
• Density independent algorithms for sparsifying k-step random walks
• I/O-efficient algorithms on triangle listing and counting
• Bounds and algorithms for graph trusses
• Triangle listing algorithms: back from the diversion
• Experimental and Efficient Algorithms
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Finding small complete subgraphs efficiently
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Tailored vertex ordering for faster triangle listing in large graphs
• Faster combinatorial \(k\)-clique algorithms
• Towards optimal set-disjointness and set-intersection data structures
• Fast approximate counting of cycles
• Join sampling under acyclic degree constraints and (cyclic) subgraph sampling
• Subgraph enumeration in optimal I/O complexity
• Join and subgraph sampling under degree constraints
• Listing 4-cycles
• When are cache-oblivious algorithms cache adaptive? A case study of matrix multiplication and sorting
• Faster combinatorial k-clique algorithms
• On triangle estimation using tripartite independent set queries
• Main-memory triangle computations for very large (sparse (power-law)) graphs

This page was built for publication: Listing triangles

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