Algorithms for some center problems on networks
The present study deals with network location problems. We examine different center problems on networks and we present some theoretical results and efficient solution algorithms. The exploitation of the network structure effects improvements in algorithms. We present a new algorithm for the absolut...
| Main Author: | |
|---|---|
| Format: | Doctoral dissertation |
| Language: | eng |
| Published: |
1984
|
| Subjects: | |
| Online Access: | https://jyx.jyu.fi/handle/123456789/103799 |
| Summary: | The present study deals with network location problems. We examine different center problems on networks and we present some theoretical results and efficient solution algorithms. The exploitation of the network structure effects improvements in algorithms. We present a new algorithm for the absolute p-center problem on tree networks. Linear time algorithms for the absolute p-center problem with p = 3 and 4 are given. For the absolute center problem we derive a new algorithm which does not need the shortest distance matrix of every pair of nodes. This makes it possible to solve absolute center problems on really large networks. Experimental results for this algorithm are also given. We also study the absolute center problem on some specific networks: networks with each edge having the same length, networks including separation nodes, and unicyclic networks. We have also generalized an absolute center definition for a subnetwork center. This new center problem is examined and solution methods are derived.
|
|---|