題目：Spanning trees with edge conflicts
We consider the problem of finding spanning trees that offer good througput communication. Namely, we are given a link graph G=(V,E) as well as a conflict graph H=(E,F) that specifies which links (edges in G) cannot be scheduled together. We seek not only a spanning tree T in G, but also a coloring of the edges of T. The objective is to minimize the number of colors used, which corresponds to finding a short schedule of the edges of the spanning tree.
We show that the solvability of this problem is closely related to a parameter of the conflict graph, known as inductive independence. In general, the problem is very hard, but becomes logarithmically-approximable when the parameter is small. We can further generalize this to finding efficient Steiner trees.
The motivation comes from wireless networking, where complex interference patterns are the norm. Our results carry over to the so-called physical model of wireless interference.
This is joint work with Guy Kortsarz, Pradipta Mitra, and Tigran Tonoyan.
題目：Degree sequences of highly-connected digraphs
By generalizing a recent result of Hong, Liu, and Lai on characterizing the degree-sequences of simple strongly connected directed graphs, we provide a characterization for degree-sequences of simple k-node-connected digraphs. More generally, we solve the directed node-connectivity augmentation problem when the augmented digraph is degree-speci ed and simple. As for edge-connectivity augmentation, we solve the special case when the edge-connectivity is to be increased by one and the augmenting digraph must be simple.