Past job offers

PhD position: job description

Location: University of Bordeaux, France
Title: graph colorings for broadcast scheduling
keywords: discrete mathematics, graph theory, broadcast scheduling
Subject: In the university of Bordeaux (France), there is a vacancy available for a position of PhD student for a period of three years, starting from September 2010. The project concerns, primarily, the development of graph coloring results dedicated to broadcast scheduling. Stable sets are widely used to model in a so-called conflict graph, mutually non-conflicting nodes in a network, with respect to some shared resource. Therefore, they allow to capture any kind of constraints: in channel assignment problems, the interference graph is such a conflict graph. Besides conflict graphs, computing the maximum size of a stable set does have natural translations in telecommunications issue: the maximum stable set problem on a connectivity graph yields the maximum broadcasting set in a TDMA framework or an activation set in a multihop radio network. In a broadcast schedule for TDMA, different time slots correspond to different colors of a suitable graph coloring: this is to be investigated in this project. The applicant should have a masterís degree in computer science, mathematics, or operations research, and possess solid knowledge in algorithms and graph theory.

Postdoc position: job description

Location: projet Mascotte INRIA Sophia-Antipolis, France
Title: Fast algorithms for graph coloring. keywords: discrete mathematics, graph theory, graph coloring,
Subject: Graph coloring plays a central role in graph theory and more generally combinatorics. It has number of applications both theoretical and practical, and in particular channel assign- ment. From the algorithmic point of view, almost every graph coloring problems are NP-hard and lots of them cannot even be approximated. It is also difficult to find exact exponential time algorithms running in time O(cn) with a small integer c. (n denotes the number of vertices of the graph.) In 1976 Lawler presented an O(2.44n) algorithm to compute an optimal proper coloring of a graph. Despite various attempts no essential improvements have been made until Bjorklund and Husfeldt and Koivisto showed that the proper graph coloring problem can be solved in time O(2n) using the Inclusion-Exclusion Principle. In addition, coloring prob- lems are generally non-Fixed Parameter Tractable with respect to the natural parameter which is the number of colors. In other words, under the classical complexity assumptions, there is no algorithm to find an optimal coloring of a graph G that runs in time f(col(G))P(n) with f an arbitrary function of the optimal number of colors col(G) and P a polynomial in the number n of vertices. The objective of the proposed work is to improve the present algorithms for graph coloring mod- elling some channel assignment problems. Several approaches are also envisaged: Inclusion- Exclusion Principle, Measure and Conquer, Branch and Reduce, ... Fixed Parameterized Algorithms must also be studied. If the natural parameters are not useful, one of the issues will be to identify parameters that could be. The applicant must have a PhD in graph theory or algorithmic. Implementation skills would be a plus.