Bounding the Size of K-tuple Covers

Document Type

Conference Proceeding

Publication Date

1-5-2009

Publication Title

42nd Hawaii International Conference on System Sciences

Publisher

IEEE

First page number:

1

Last page number:

8

Abstract

Suppose there are n applications and n processors. A pair cover is a set S of one-to-one mappings (assignments) of the applications to the processors such that, for every pair (Ai,Aj) of applications and every pair (p,q) of processors, there is an assignment f in S that maps (Ai,Aj) to (p,q). More generally, we consider, for all k/spl ges/1, minimum size k-tuple covers. We improve bounds given earlier in by Latifi, where the application for k-tuple covers was fault tolerance of the multidimensional star network. Let F(n,k) denote the minimum cardinality k-tuple cover for n applications and processors. We give bounds for F(n,k) that are within a small multiplicative factor of optimum.

Keywords

Application software; Computer science; Drugs; Fault tolerance; Medical tests; Multidimensional systems; Polynomials; Sampling methods; Upper bound; Zinc

Disciplines

Electrical and Computer Engineering | Engineering

Language

English

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.

UNLV article access

Search your library

Share

COinS