Minimal Equivalent Subgraphs Containing a Given Set of Arcs
Please always quote using this URN:urn:nbn:de:0296-matheon-12790
- 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.
Author: | Arne C. Reimers, Alexandra M. Reimers, Yaron A.B. Goldstein |
---|---|
URN: | urn:nbn:de:0296-matheon-12790 |
Referee: | Alexander Bockmayr |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2014/03/27 |
Release Date: | 2014/03/27 |
Tag: | Directed graph; Minimal equivalent subgraph; Transitive closure; Transitive reduction |
Institute: | Research Center Matheon |
Freie Universität Berlin | |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C20 Directed graphs (digraphs), tournaments |
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05] | |
Preprint Number: | 1053 |