5 papers
Curves, points, incidences and covering
Arijit Bishnu, Mathew Francis, Pritam Majumder
Given a point set, mostly a grid in our case, we seek upper and lower bounds on the number of curves that are needed to cover the point set. We say a curve covers a point if the cu…
Optimal non-adaptive algorithm for edge estimation
Arijit Bishnu, Debarshi Chanda, Buddha Dev Das +2
We present a simple nonadaptive randomized algorithm that estimates the number of edges in a simple, unweighted, undirected graph, possibly containing isolated vertices, using only…
Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
The degree distribution of a graph , , is one of the most fundamental objects of study in the analysis of graphs as it embodies relationship among entities.…
Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
Given a simple, unweighted, undirected graph with and , and parameters , along with \texttt{Degree}, \texttt{Neighbour}, \texttt{Edg…
Near Uniform Triangle Sampling Over Adjacency List Graph Streams
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
Triangle counting and sampling are two fundamental problems for streaming algorithms. Arguably, designing sampling algorithms is more challenging than their counting variants. It m…