Back to results
University of Illinois at Urbana-Champaign
Equitable List Coloring, Induced Linear Forests, and Routing in Rooted Graphs
Abstract
dc:descriptionWe 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.
Degree
thesis:*- Name thesis:degree_name
- Ph.D.
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics
- Grantor
- University of Illinois at Urbana-Champaign
- Year dc:date
- 2015
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Pelsmajer, Michael Joshua
- Contributors dc:contributor
-
- West, Douglas B.
Subjects
dc:subject × 1Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- (MiAaPQ)AAI3070412
- OAI identifier oai:identifier
- oai:www.ideals.illinois.edu:2142/86805