Network Modelling Meeting

[Joseph Peters <peters@cs.sfu.ca>]

NETWORK MODELLING GROUP

Friday, March 21, 14:00, ASB 9705

Speaker:  Zhengbing Bian
	  School of Computing Science

Title:    Path Coloring on Trees of Rings

Abstract: see below

Juice and cookies will be provided.
____________________________________________________________________________

ABSTRACT

A tree of rings is an undirected graph obtained by interconnecting
rings in a tree structure such that any two rings intersect in at
most one node and any two nodes are connected by exactly two
edge-disjoint paths. Given a set of paths on a tree of rings with
maximum node degree 8 and maximum edge load L, we show
that 3L is the sufficient number of colors to color the paths such
that any two paths sharing an edge are assigned different colors.
3L is also necessary, even the node degree is only 4. We also show
that 2.5w is enough for tree of rings of degree at most 6, where
w is the maximum number of paths each pair of which intersect with
each other. There is a trivial O(logN)-competitive algorithm for
online path coloring on tree of rings with N nodes.