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
APPRENTISSAGE ET OPTIMISATION SUR LES GRAPHES


ANALYSE DE DONNéES MULTI-MODALES POUR LES PATHOLOGIES COMPLEXES PAR LA CONCEPTION ET L’IMPLéMENTATION DE PROTOCOLES REPRODUCTIBLES ET RéUTILISABLES


DESIGNING INTERACTIVE TOOLS FOR CREATORS AND CREATIVE WORK
Creative work has been at the core of research in Human-Computer Interaction (HCI). I describe the results of a series of studies that look at how creators work, where creators include artists with years of professional practice, as well as learners, or novices and casual makers. My research focuses on three creation activities: drawing, physical modeling, and music composition. For these activities, I examine how artists switch between representations and how these representations evolve throughout their creative process, from early sketches to fine-grained forms or structured vocabularies. I present interactive systems that enrich their workflow (i) by extending their computer tools with physical user interfaces, or (ii) by making physical materials interactive. I also argue that sketch-based representations can allow for user interfaces that are more personal and less rigid. My presentation will reflect on lessons and limitations of this work and discuss challenges for future design-support tools.