I/O-efficient algorithms on triangle listing and counting

DOI10.1145/2691190.2691193MaRDI QIDQ5012504zbMATH OpenOpenAlexFDO

Authors Xiaocheng Hu, Yufei Tao, Chin-Wan Chung

Publication date 25 November 2021

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

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

zbMATH Keywords

graphsI/O-efficient algorithmstriangle countingtriangle listing

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Experimental and Efficient Algorithms
• iTri: index-based triangle listing in massive graphs
• Triangle listing algorithms: back from the diversion
• Listing triangles
• Main-memory triangle computations for very large (sparse (power-law)) graphs

Cited in

(6)

• iTri: index-based triangle listing in massive graphs
• An efficient exact algorithm for triangle listing in large graphs
• Summarized bit batch-based triangle listing in massive graphs
• Triangle listing algorithms: back from the diversion
• Towards optimal dynamic indexes for approximate (and exact) triangle counting
• I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration

This page was built for publication: I/O-efficient algorithms on triangle listing and counting

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