Algorithmic and Theoretical Developments for Vertex Partitioning Problems

Michael U. Gerber, DMA, Ecole Polytechnique Fédérale de Lausanne

We consider different problems arising in graph theory, more particularly vertex partitioning problems. In general, we want to partition the set of vertices of a graph into several subsets in order to respect some specific constraints. This fundamental problem finds many applications in practice, such as time tabling, scheduling, and resource assignment problems. Moreover, the frequency assignment problem has received a lot of attention during the recent telecommunications revolution.

In the first chapter, we consider the maximum stable set problem, which is a classical NP-hard problem in combinatorial optimization. We make a survey of the graph classes for which a polynomial time algorithm is known. Furthermore, we propose several new, more general, results. Our approach consists in applying some graph transformation, which might delete or add vertices or edges to the graph, and decreases the stability number by a given constant. The idea is then to iteratively apply this transformation to a given graph until we obtain a transformed graph for which we know how to calculate the stability number.

One of the interests of extremal graph theory is to characterize the structural properties of graphs. The idea is to observe the relationships between various parameters of a graph, such as the number of vertices, the number of edges, the chromatic number or the stability number. We would like to know how these different parameters interact. In particular, we may want to know how a parameter can vary, if some other parameters are constant. Turán's Theorem, proved in 1941, is one of the fundamental results in extremal graph theory. The theorem answers the following question: if the number of vertices and the size of a maximum stable set of a graph are known, then what is the minimum number of edges in the graph? In the second chapter, we prove a similar result for the 2-stability number of a graph, which is defined as the largest number of vertices in a 2-colorable subgraph.

In the third chapter, we introduce a new graph partitioning problem, called the Satisfactory Graph Partitioning problem. In a given graph, we want to partition its vertex set into two non-empty subsets, such that each vertex is adjacent to at least as many vertices in its own subset as in the other. This problem corresponds to a situation where we have to separate a group of persons, or objects, into two non-empty groups such that every person or object has at least as many reasons to stay in his own group, as he has to change. Such a solution corresponds to an equilibrium situation. We study the complexity of this graph partitioning problem.

The problems mentioned above all have a common nature: we want to partition the vertices of a graph with respect to certain additional constraints. In the last chapter of this thesis, we define a framework in order to describe such vertex partitioning problems. We propose a polynomial time algorithm on classes of graphs with bounded clique-width for all optimization problems contained in the framework.

For further information, please contact

[Top] 

Méthode tabou pour un problème d'affectation de fréquences avec polarisations

David Schindl, DMA, Ecole Polytechnique Fédérale de Lausanne

Les demandes en communication sans cesse croissantes du fait de l'augmentation du nombre des utilisateurs et de l'apparition de nouveaux besoins, combinées au caractère inextensible de la ressource spectrale disponible rendent de plus en plus difficiles la tâche d'allocation de fréquences. Aussi la gestion optimale des fréquences devient un point essentiel pour le déploiement et l'administration des réseaux tant civils que militaires.

Le CELAR en tant que centre technique de la Délégation Générale pour l'Armement (DGA) est chargé dans le cadre de programmes d'armement ou d'études amonts de la réalisation et du suivi d'une partie des travaux visant à optimiser l'utilisation du spectre au sein des forces armées françaises. Ce problème traité dans le projet CALMA (Combinatorial Algorithms for Military Applications) dans les années 93-95 a été enrichi pour prendre en compte les notions de polarisation et de relâchement contrôlés des contraintes de compatibilité électromagnétique.

Dans ce contexte, la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF) propose un concours dont le sujet traite de l'allocation de fréquences dans les réseaux de télécommunication par voies hertziennes. Le but de ce concours est d'implémenter un algorithme à la fois rapide et fournissant une bonne solution à un problème d'optimisation concernant l'affectation de fréquences avec polarisations. Cet algorithme est testé sur une heure de temps CPU et un jury décide en se basant sur trois critères, à savoir la qualité des résultats fournis, la rapidité avec laquelle ils sont obtenus et la rigueur des réponses fournies (preuves d'optimalité), quels sont les meilleurs algorithmes.

De nombreuses techniques ont été développées pour résoudre ce type de problèmes, et ce concours donnera l'occasion de les comparer sur un pied d'égalité. Les membres de la Chaire de Recherche Opérationnelle Sud Est (ROSE) du Département de Mathématiques de l'EPFL sont particulièrement expérimentés dans une méthode bien connue dans le domaine, appelée tabou. Pour tirer le meilleur de ce procédé, une certaine quantité de travail est nécessaire d'une part pour implémenter les bases de la méthode, et d'autre part pour analyser les résultats fournis et tenter d'apporter à l'algorithme des améliorations par des moyens déjà existants ou non. Cette partie du travail est la plus importante mais aussi la plus intéressante, puisqu'elle demande à la fois du bon sens et de la créativité.

Le but de ce projet de diplôme est précisément de créer une version de l'algorithme tabou suffisamment efficace pour permettre à l'équipe du ROSE de faire bonne figure dans le concours susmentionné, c'est-à-dire au moins de se qualifier pour la deuxième phase du challenge.

For further information, please contact

Besuch des Paketzentrums in Härkingen

Die Führung beginnt um 13.30 Uhr. Im Showroom (Besucherpavillon) werden wir zuerst eine kurze Folienpräsentation der Schweizerischen Post anschauen, ca. 20 Minuten, danach werden wir einen Videofilm angucken wie ein Paket von A nach B kommt, ca. 10 Minuten. Anschliessend werden wir auf den Rundgang durch das Paketzentrum gehen, dies dauert ungefähr eine Stunde. Am Schluss des Rundgangs laden wir Sie herzlich zu einem Getränk und einem Süssgebäck ein.

Visite du centre de tri postal de Härkingen

La visite commencera à 13h30. Dans le Showroom (pavillon des visiteurs), nous vous ferons une brève présentation de la Poste suisse (environ 20 minutes), puis nous vous présenterons une vidéo expliquant comment un paquet est acheminé du point A au point B (environ 10 minutes). Nous poursuivront par une visite du centre de tri postal, qui durera approximativement une heure. A la fin de la visite, nous vous convierons cordialement à une verrée.

Denise Blösch, Kommunikation-Sekretariat, Die Schweizerische Post