Files in this item

FilesDescriptionFormat

application/pdf

application/pdf3070412.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF

Description

Title:Equitable List Coloring, Induced Linear Forests, and Routing in Rooted Graphs
Author(s):Pelsmajer, Michael Joshua
Doctoral Committee Chair(s):West, Douglas B.
Department / Program:Mathematics
Discipline:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(s):Mathematics
Abstract:We explicitly characterize the family of networks for which such a protocol exists. This characterization is given in terms of forbidden rooted minors, which leads to a linear time recognition algorithm for this family of networks. We obtain a similar characterization for the family of networks in which a message can be broadcast from a single node s to all other nodes. Finally, we show that there is a forbidden rooted minor characterization for the more general case when a header (containing routing information) of fixed length is attached to the message, and we discuss the algorithmic consequences of this characterization.
Issue Date:2002
Type:Text
Language:English
Description:98 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2002.
URI:http://hdl.handle.net/2142/86805
Other Identifier(s):(MiAaPQ)AAI3070412
Date Available in IDEALS:2015-09-28
Date Deposited:2002


This item appears in the following Collection(s)

Item Statistics