Dissertation/Thesis Abstract

Relaxations of L(1,1)-labeling for the broadcast scheduling problem
by Joseph, Shaun N., Ph.D., University of Rhode Island, 2011, 90; 3449951
Abstract (Summary)

The broadcast scheduling problem asks how an arbitrary network of broadcast transceivers operating on a shared medium may share the medium in such a way that communication over the entire network is possible. In the case where transmissions are explicitly scheduled, as opposed to be determined by contention, the problem is naturally modeled as a graph coloring problem. The canonical model is the L(1, 1)-labeling, also known as the distance-2 coloring, coloring of the graph square, or strict schedule. This coloring is, however, difficult to obtain even sub-optimally and typically uses many colors, which corresponds to an undesirable over-division of the medium.

This work introduces a relaxation of L(1, 1)-labeling called (1, 1)-labeling or the pseudo-schedule. Whereas strict schedules guarantee that every path in the graph is a communication path, pseudo-schedules only require the existence of a communication path between any two vertices. The study shows that pseudo-schedules have many superior characteristics to the canonical model, provided the relaxation is acceptable. In particular, the worst case number of colors used is linear in the degree of the graph, as opposed to quadratic for strict schedules.

The formal properties of the (1, 1)-labeling are comprehensively treated, including investigations of its “chromatic number,” rigorous analysis of several algorithms, and proofs of hardness of optimization and approximation. Basic results on a generalization of the coloring are obtained, and nine open problems are posed for future research.

Indexing (document details)
Advisor: DiPippo, Lisa
Commitee: Eaton, Nancy, Henry, Timothy, Lamagna, Edmund, Sun, Yan
School: University of Rhode Island
Department: Applied Mathematical Sciences
School Location: United States -- Rhode Island
Source: DAI-B 72/06, Dissertation Abstracts International
Subjects: Applied Mathematics, Computer science
Keywords: Broadcast scheduling, Graph coloring, Graph theory, Medium access control, Time division multiple access, Wireless sensor networks
Publication Number: 3449951
ISBN: 978-1-124-57919-1
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy