Graph Simplification for Infrastructure Network Design
| Autor: | Sean Yaw, Richard S. Middleton, Brendan Hoover |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Combinatorial Optimization and Applications ISBN: 9783030364113 COCOA |
| DOI: | 10.1007/978-3-030-36412-0_47 |
| Popis: | Network design problems often involve scenarios where there exist many possible routes between fixed vertex locations (e.g. building new roads between cities, deploying communications and power lines). Many possible routes in a network result in graph representations with many edges, which can lead to difficulty running computationally demanding optimization algorithms on. While producing a subgraph with a reduced number of edges would in itself be useful, it is also important to preserve the ability to interconnect vertices in a cost effective manner. Suppose there is a set of target vertices in a graph that needs to be part of any size-reduced subgraph. Given an edge-weighted, undirected graph with n vertices, set of target vertices T, and parameter \(k \ge 1\), we introduce an algorithm that produces a subgraph with the number of edges bounded by \(\min \{O(n\frac{n^{1/k}}{\left| {T}\right| }), O(n\left| {T}\right| )\}\) times optimal, while guaranteeing that, for any subset of the target vertices, their minimum Steiner tree in the subgraph costs at most 2k times the cost of their minimum Steiner tree in the original graph. We evaluate our approach against existing algorithms using data from Carbon Capture and Storage studies and find that in addition to its theoretical guarantees, our approach also performs well in practice. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|