Computer Science – Discrete Mathematics
Scientific paper
2003-05-28
Computer Science
Discrete Mathematics
15 pages, 13 figures. Presented at the SIAM Discrete Math 2002 conference
Scientific paper
The bandwidth of a graph is the labeling of vertices with minimum maximum edge difference. For many graph families this is NP-complete. A classic result computes the bandwidth for the hypercube. We generalize this result to give sharp lower bounds for products of cliques. This problem turns out to be equivalent to one in communication over multiple channels in which channels can fail and the information sent over those channels is lost. The goal is to create an encoding that minimizes the difference between the received and the original information while having as little redundancy as possible. Berger-Wolf and Reingold [2] have considered the problem for the equal size cliques (or equal capacity channels). This paper presents a tight lower bound and an algorithm for constructing the labeling for the product of any number of arbitrary size cliques.
Berger-Wolf Tanya Y.
Harris Mitchell A.
No associations
LandOfFree
Sharp Bounds for Bandwidth of Clique Products does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sharp Bounds for Bandwidth of Clique Products, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp Bounds for Bandwidth of Clique Products will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-607286