HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is there a name for the problem of turning a bipartite graph into two graphs?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthegraphintographsbipartiteturningtwonamefor

Problem

Is there a name for the problem of turning a bipartite graph into two graphs in the following way? We form one graph from the vertices on the left, such that two vertices are made adjacent if they share a common neighbour on the right; we form the other graph similarly from the vertices on the right.

This pops up, for example, when finding collaboration relationships in a bipartite graph from scientists to papers or actors to movies.

This being a common problem, I wonder if it has a common name, and maybe specific literature on it.

Solution

You're (basically) computing the square of the graph, in which two vertices are adjacent if there is a path of length 2 (or at most 2, depending on the definition) connecting them. The square will contain at least two connected components, corresponding to the two bipartitions.

Context

StackExchange Computer Science Q#62701, answer score: 5

Revisions (0)

No revisions yet.