3
$\begingroup$

I'm currently documenting an algorithm which involves deleting a node in a directed dependency graph while maintaining the implied dependencies between its parents and children.

Take for example the following graph:

Before and after node deletion

Edges are added from all parents to children before node X is deleted to ensure that the implied dependencies are maintained.

Question: Is there a standard terminology for such an operation?


Update: Thanks to a change in my algorithm, node X is now guaranteed to have only one parent. This reduces the above operation to a simple node contraction with the parent. While my immediate problem is now solved, I'm leaving the question open and unanswered as I'm still curios to know the solution had my requirements not changed.

  • 0
    What ever happened with this? Did you ever find what you were looking for?2015-01-12

2 Answers 2

2

bipartite or multimodal projection

1

The Wikipedia page on graph subdivision refers to this procedure as smoothing. They restrict it to vertices of degree 2 (in which case the old graph was a subdivision of the new graph), so this might not be an exact fit.

A related procedure is edge contraction; that page also mentions vertex contraction, but that is different from what is called for here.

  • 0
    @jp26 ver$t$ex subsumptio$n$... I like that.2012-09-03