Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
Daniel Paul-Pena, C. Seshadhri
We study the classic problem of subgraph counting, where we wish to determine the number of occurrences of a fixed pattern graph in an input graph of vertices. Our focu…
cs.SI2024
Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets
Sabyasachi Basu, Daniel Paul-Pena, Kun Qian +3
Graphs are a fundamental data structure used to represent relationships in domains as diverse as the social sciences, bioinformatics, cybersecurity, the Internet, and more. One of…
cs.DS2024
Improved Massively Parallel Triangle Counting in Rounds
Quanquan C. Liu, C. Seshadhri
In this short note, we give a novel algorithm for round triangle counting in bounded arboricity graphs. Counting triangles in rounds (exactly) is listed as one of the…