TY - GEN A1 - Reimers, Arne C. A1 - Reimers, Alexandra M. A1 - Goldstein, Yaron A.B. T1 - Minimal Equivalent Subgraphs Containing a Given Set of Arcs N2 - 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′ ⊆ 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 polynomial time. KW - Directed graph KW - Transitive reduction KW - Transitive closure KW - Minimal equivalent subgraph Y1 - 2014 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/1279 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-12790 ER -