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 |
