<< Enumeration in Graphs and Hypergraphs : Algorithms and Complexity >>
The ANR project GraphEn deals with enumeration problems. Contrary to the ubiquitous optimization problems, the task in enumeration problems is to enumerate all objects of the input satisfying a certain property. In our research the number of those objects is usually exponential in the input size.
The classical approach is said to be output-sensitive and measures the running time in the size of the input and the output. A major goal is to construct algorithms of polynomial delay. The recent input-sensitive approach measures the running time in the size of the input. Hence such algorithms are exact exponential ones. This latter approach can also be used to establish upper bounds on the number of objects enumerated. Enumeration is a young field in algorithms with hopefully many new ideas and techniques to be found. Combining enumeration with other algorithmic approaches, as e.g. parameterized algorithms, will be studied as well.
Background in enumeration algorithms or exact exponential algorithms would be an asset. Candidates should have a strong background in construction and analysis of algorithms. Background in graphs and graph algorithms is highly desirable. Knowledge in discrete mathematics and graph theory is appreciated.
Candidates should have a Master's degree in Computer Science or related fields. The grant is a standard french PhD support. The gross salary is 1684 euros and it may be increased by teaching (in french).
Applications (including CV, letter of motivation, letter of recommendation) should be send to Dieter Kratsch, the supervisor of the PhD project, at dieter.kratsch@univ-lorraine.fr no later than june 15, 2016. English is required language. French may be useful in every day life, teaching, etc.
The city of Metz is located in the east of France 60 kilometers from Saarbrücken (Germany) and 60 kilometers from Luxembourg City. By TGV one can go to Paris in 1 hour and 20 minutes.
Informal inquiries to the above e-mail address are also welcome. Further information is available at
ANR GraphEn : http://graphen.isima.fr
Dieter Kratsch
Université de Lorraine
LITA, Metz
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
