科研之友
微信
新浪微博
Facebook
分享链接
摘要
Transitive reductions and minimal equivalent subgraphs have proven to be a powerful concept to simplify networks and to measure their redundancy. Here we consider a generalization of the minimal equivalent subgraph problem where a set of arcs is already given. For two digraphs D = (V, A), D' = (V, A') with A' subset of A, we ask for the minimal set of edges of D that have to be added to D' such that the transitive closure of D equals the transitive closure of D'. We present a method to compute such an extension and show that if D is transitively closed, this problem can be solved in the same asymptotic time as computing a transitive reduction of D.
- 出版日期2017-5-2
