All geek questions in one place

New or less well-known data structures for network (graphical) data?

What are even more interesting graphical data structures for working with networks? I'm interested in structures that can offer a certain advantage in terms of moving around the network, searching for random nodes, size in memory, or for inserting / deleting / temporarily hiding nodes, for example.

Note. I'm not so interested in databases as projects for solving problems with external memory.

+3
source share
2 answers

One of my personal favorites is a link / cut tree , a data structure for splitting a graph into a family of oriented trees. This allows you to solve network flow problems asymptotically faster than more traditional methods, and can be used as a more powerful generalization of the union / find structure that you may have heard about before.

+2
source

I heard about Skip Graphs ( http://www.google.com/search?ie=UTF-8&oe=UTF-8&sourceid=navclient&gfns=1&q=skip+graphs ), a probabilistic graph structure that, as far as I know, is already there to use in some peer-to-peer applications.

, . , : http://www14.informatik.tu-muenchen.de/personen/jacob/Publications/podc09.pdf

+1

Source: https://habr.com/ru/post/1787752/

More articles:


All Articles