Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations?

  • Insert an edge into the graph
  • Delete an edge from the graph
  • Given a query edge $(i,j)$, list all the triangles that include that edge. There can be $n$ of these in the worst case but ideally this operation would be sublinear if the number of triangles to be reported is.
  • $\begingroup$ I haven't looked at it very closely, but maybe the techniques in this paper arxiv.org/abs/1804.02780 can be used for your kind of queries? $\endgroup$ – M.Monet Jul 3 '19 at 21:55
  • $\begingroup$ Is the graph sparse or dense? (Or can be any?) $\endgroup$ – Cyriac Antony Jul 4 '19 at 8:32
  • $\begingroup$ @CyriacAntony It can be any as you suggest. $\endgroup$ – user15587 Jul 4 '19 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy