On mapping processes to processors in distributed systems
This paper is concerned with the implementation of parallel programs on networks of processors. In particular, we study the use of the network augmenting approach as an implementation tool. According to this approach, the capabilities of a given network of processors can be increased by adding some auxiliary links among the processors. We prove that the minimum set of edges needed to augment a line-like network so that it can accommodate a parallel program is determined by an optimal path cover of the graph representation of the program. An optimal path cover a simple graph G is a set of vertex-disjoint paths that cover all the vertices of G and has the maximum possible number of edges. We present a linear time optimal path covering algorithm for a class of sparse graphs. This algorithm is of special interest since the optimal path covering problem is NP-complete for general graphs. Our results suggest that a ``cover and augment scheme can be used for optimal implementation of parallel programs in line-like networks.
- Augmentation Problems
- Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
- scientific article; zbMATH DE number 3467157 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Optimal Sorting Algorithms for Parallel Computers
- Quotient Networks
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Optimal covering of cacti by vertex-disjoint paths
- An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
- Path covering problems and testing of printed circuits
- On the \(k\)-path cover problem for cacti
- Finding a minimum path cover of a distance-hereditary graph in polynomial time
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- On the properties of a tree-structured server process
- scientific article; zbMATH DE number 1690154 (Why is no real title available?)
- Differential approximation results for the traveling salesman and related problems
- On mapping production systems onto multiprocessors
- Towards a Visual Definition of a Process in a Distributed Environment
- scientific article; zbMATH DE number 107996 (Why is no real title available?)
- Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
- Parameterizing path partitions
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Parameterizing path partitions
- An efficient algorithm to construct disjoint path covers of DCell networks
This page was built for publication: On mapping processes to processors in distributed systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095652)
