Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

Ph.D
Group : Algorithms and Complexity

Proper and Weak Proper Trees in edge-colored graphs and multigraphs

Starts on 01/10/2007
Advisor : MANOUSSAKIS, Yannis

Funding : A
Affiliation : Université Paris-Sud
Laboratory : LRI

Defended on 30/09/2011, committee :
Directeur:
* Yannis MANOUSSAKIS Professeur, Université Paris-Sud 11

Rapporteurs:
* Eric ANGEL Professeur, Université d'Évry
* Eric SOPENA Professeur, Université Bordeaux 1

Examinateurs:
* Dominique BARTH Professeur, Université de Versailles
* Marina GROSHAUS Professeur, Université de Buenos Aires,
* Hao LI Directeur de Recherche (CNRS), Université Paris-Sud 11

Research activities :

Abstract :
In this thesis, we investigate the extraction of trees from edge-colored
graphs. We focus on finding trees with properties based on coloring.
Namely, we deal with proper and weak proper spanning trees, denoted PST
and WST.
• We show the optimization versions of these problems to be NP-hard in
the general case of edge-colored graphs and we provide algorithms to
find these trees in the case of edge-colored graphs without properly
edge-colored cycles. We also provide some nonapproximability bounds.
• We investigate the existence of a PST in the case of edge-colored
graphs under certain conditions on the graph, both structural and
related to the coloration. We consider sufficient conditions that
guarantee the existence of a PST in edge-colored (not necessarily
proper) graphs with any number of colors. The conditions we consider are
combinations of various parameters such as: total number of colors,
number of vertices, connectivity and the number of incident edges of
different colors to the vertices.
• We then consider properly edge-colored Hamiltonian paths in the
edge-colored multigraphs, which are relevant to our study since they are
also PST. We establish sufficient conditions for a multigraph to contain
a proper edge-colored Hamiltonian path, depending on several parameters
such as the number of edges, the degree of edges, etc.
• Since one of the sufficient conditions for the existence of proper
spanning trees is connectivity, we prove several upper bounds for the
smallest number of colors needed to color a graph such that it is
k-proper-connected. We state several conjectures for general and

Ph.D. dissertations & Faculty habilitations
DECODING THE PLATFORM SOCIETY: ORGANIZATIONS, MARKETS AND NETWORKS IN THE DIGITAL ECONOMY
The original manuscript conceptualizes the recent rise of digital platforms along three main dimensions: their nature of coordination devices fueled by data, the ensuing transformations of labor, and the accompanying promises of societal innovation. The overall ambition is to unpack the coordination role of the platform and where it stands in the horizon of the classical firm – market duality. It is also to precisely understand how it uses data to do so, where it drives labor, and how it accommodates socially innovative projects. I extend this analysis to show continuity between today’s society dominated by platforms and the “organizational society”, claiming that platforms are organized structures that distribute resources, produce asymmetries of wealth and power, and push social innovation to the periphery of the system. I discuss the policy implications of these tendencies and propose avenues for follow-up research.

DISTRIBUTED COMPUTING WITH LIMITED RESOURCES


VALORISATION DES DONNéES POUR LA RECHERCHE D'EMPLO