Efficient parallel algorithms for r-dominating set and p-center problems on trees
From MaRDI portal
Publication:1262780
DOI10.1007/BF01840381zbMath0686.68054MaRDI QIDQ1262780
Publication date: 1990
Published in: Algorithmica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Theory of operating systems (68N25)
Related Items
An algorithm to find two distance domination parameters in a graph, A centroid labelling technique and its application to path selection in trees
Cites Work
- Routing, merging, and sorting on parallel models of computation
- The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
- An optimally efficient selection algorithm
- A linear algorithm for the domination number of a tree
- New Results on the Complexity of p-Centre Problems
- An Efficient Parallel Biconnectivity Algorithm
- Binary tree algebraic computation and parallel algorithms for simple graphs
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
- Polynomially bounded algorithms for locatingp-centers on a tree
- An $O ( ( n\log p )^2 )$ Algorithm for the Continuous p-Center Problem on a Tree
- R -Domination in Graphs
- Slowing down sorting networks to obtain faster sorting algorithms
- A simple parallel tree contraction algorithm
- Finding kth paths and p-centers by generating and searching good data structures
- Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
