𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of some arborescences finding problems on a multihop radio network

✍ Scribed by Nen-Fu Huang; Tsing-Her Huang

Publisher
Springer Netherlands
Year
1989
Tongue
English
Weight
284 KB
Volume
29
Category
Article
ISSN
0006-3835

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the complexity of finding common appr
On the complexity of finding common approximate substrings
✍ Patricia A. Evans; Andrew D. Smith; H.Todd Wareham πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 323 KB

Problems associated with ΓΏnding strings that are within a speciΓΏed Hamming distance of a given set of strings occur in several disciplines. In this paper, we use techniques from parameterized complexity to assess non-polynomial time algorithmic options and complexity for the COMMON APPROXIMATE SUBST

On the complexity of some geometric prob
On the complexity of some geometric problems in unbounded dimension
✍ Nimrod Megiddo πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 429 KB

This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by unit ball% and (iii) minimum number of lines to hit a set of balls. Each of these problems is proven no

On the Complexity of Some Problems on Gr
On the Complexity of Some Problems on Groups Input as Multiplication Tables
✍ David Mix Barrington; Peter Kadau; Klaus-JΓΆrn Lange; Pierre McKenzie πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 131 KB

The Cayley group membership problem (CGM) is to input a groupoid (binary algebra) G given as a multiplication table, a subset X of G, and an element t of G and to determine whether t can be expressed as a product of elements of X. For general groupoids CGM is P-complete, and for associative algebras