patternMinor
Is there a name for the problem of turning a bipartite graph into two graphs?
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.
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.