11
$\begingroup$

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.
Improve this question
$\endgroup$
3
  • $\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, 2019 at 21:55
  • $\begingroup$ Is the graph sparse or dense? (Or can be any?) $\endgroup$
    – Cyriac Antony
    Jul 4, 2019 at 8:32
  • $\begingroup$ @CyriacAntony It can be any as you suggest. $\endgroup$
    – user15587
    Jul 4, 2019 at 18:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.