- Renseignements pratiques
- Enseignement
Contact
LIFO - Bâtiment IIIA
Rue Léonard de Vinci
B.P. 6759
F-45067 ORLEANS Cedex 2
Email:
contact.lifo
Tel: +33 (0)2 38 41 99 29
Fax: +33 (0)2 38 41 71 37
Accéder aux Rapports de l'année : 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018
RR-2007-01 Performance Evaluation of a Parallel Algorithm for "GroupBy-Join" Queries Processing in Distributed Architectures
M. Al Hajj Hassan et M. Bamha
Résumé : SQL queries involving join and group-by operations are fairly common in many decision support applications where the size of the input relations is usually very large, so the parallelization of these queries is highly recommended in order to obtain a desirable response time. Several parallel algorithms that treat this kind of queries have been presented in the literature. However, their most significant drawbacks are that they are very sensitive to data skew and involve expensive communication and Input/Output costs in the evaluation of the join operation. In this paper, we present an algorithm that overcomes these drawbacks because it evaluates the "GroupBy-Join" query without the need of the direct evaluation of the costly join operation, thus reducing its Input/Output and communication costs. The performance of this algorithm is analyzed using the scalable and portable BSP (Bulk Synchronous Parallel) cost model which predicts a near optimal linear speedup even for highly skewed data. These performance predictions were also validated by the implementation results.
Mot(s) Clé(s) : PDBMS, Parallel joins, Data skew, Join product skew, GroupBy-Join queries, BSP cost model.
RR-2007-02 Intruders with Caps
S. Anantharaman, P. Narendran, M. Rusinowitch
Résumé : In the analysis of cryptographic protocols, a treacherous set of terms is one from which an intruder can get access to what was intended to be secret, by adding on to the top of a sequence of elements of this set, a cap formed of symbols legally part of his/her knowledge. In this paper, we give sufficient conditions on the rewrite system modeling the intruder's abilities, such as using encryption and decryption functions, to ensure that it is decidable if such caps exist. The following classes of intruder systems are studied: linear, dwindling, \Delta-strong, and optimally reducing; and depending on the class considered, the cap problem (``find a cap for a given set of terms'') is shown respectively to be in P, NP-complete, decidable, and undecidable.
Mot(s) Clé(s) :
RR-2007-03 Performance Prediction for Distributed Virtual Reality Applications Mappings on PC Clusters
Sylvain Jubertie, Emmanuel Melin
Résumé : Large and distributed Virtual Reality applications are often built from heterogeneous parallel codes. FlowVR offers a design model to easily compose a loosely coupled VR distributed application. FlowVR highly facilitates the development of this kind of applications making possible the description of their coupling and their mapping on the cluster nodes independently of their code. Nevertheless, the choice of a good mapping is leaved to the developer skill. In an other hand, VR applications may include lots of different components and clusters may also be composed of numerous and heterogeneous nodes and networks. In this case it seems very difficult to map efficiently a distributed VR aplication onto a large cluster without tools to help the programmer to analyse his choices. The FlowVR design, particularly does not propose any kind of performance model. In this paper we present an approach to determine performances of VR applications from a FlowVR network and from caracteristics of a cluster. We also give some advices to the developer to design efficient FlowVR mappings. Since FlowVR model is very closed to underlying models of lots of VR codes, our approach can be useful for all designers of such applications.
Mot(s) Clé(s) :
RR-2007-04 Faithful embedding on finite orders classes
Alain Guillet, Jimmy Leblet, Jean-Xavier Rampon
Résumé : Nous étudions, dans le cadres des classes d'ordres finis, la notion d'extension respectueuse pour les relations, notion introduite en 1971 par R. Fraïssé. Cette notion permet d'étudier, à travers les sous-structures interdites, les relations d'ordres d'une manière inhabituelle et met ainsi en lumière des caractéristiques structurelles spécifiques. Dans ce papier, nous montrons que, pour la plus part des classes d'ordres connues, n'importe quel ordre appartenant à cette classe admet une extension respectueuse appartenant aussi à cette classe.
Mot(s) Clé(s) : extension, extension respectueuse, isomorphisme, ordres finis, ordres partiels, plongement.
RR-2007-05 Inductive Characterizations of Finite Interval Orders and Semiorders
Jimmy Leblet, Jean-Xavier Rampon
Résumé : Nous introduissons des définitions inductives de deux classes d'ordres. Par des preuves simples, nous prouvons que l'une d'elles correspond à la classe des ordres d'intervalles finis et que l'autre est exactement la classe des semi-ordres. Pour conclure, on considère les principaux théorèmes de caractérisations de ces classes et donnons des preuves simples et directes d'équivalence avec nos caractérisations.
Mot(s) Clé(s) : antichaîne, caractérisation, décomposition, définition inductive, ordres d'intervalles, ordres finis, ordres partiels, semi-ordres.
RR-2007-06 Towards a Resource-Safe Erlang
David Teller
Résumé : Lentement mais sûrement, l'industrie découvre le besoin de langages de programmation, d'environnements d'exécution et de méthodologies adaptées au développement d'applications collaboratives et distribuées. Malheureusement, à l'heure actuelle, les plate-formes disponibles pour ces applications restent fragiles vis-à-vis d'un grand nombre de situations, en particulier les attaques d'épuisement de ressources et de Déni de Service, et ne peuvent répondre à ces attaques, au mieux, que cas par cas. Au cours de ce travail, nous avons étudié le problème de la gestion des ressources dans le langage Erlang : comment fournir des services, utilisables à travers le réseau, tout en s'assurant que des tierces-parties mal intentionnées ne pourront pas manipuler ces points d'entrée dans le système pour monopoliser l'intégralité de la mémoire vive, de la table des fichiers ou de toute autre ressource limitée et critique ? Pour contribuer à répondre à cette question, nous produisons une sémantique formelle de Core Erlang, un modèle de certaines fonctions de sa bibliothèque standard, auxquels nous associons un système de types conçu pour prouver formellement la robustesse de services vis-à-vis d'attaques de Déni de Service.
Mot(s) Clé(s) : Systèmes distribués, Attaques de Déni de Service, Algèbres de Processus, Systèmes de Types, Analyse Statique, Ressources, Erlang, pi-calcul
RR-2007-07 Mapping and Performance Prediction for Distributed Applications on Heterogeneous Clusters
Sylvain Jubertie, Emmanuel Melin
Résumé : Distributed applications running on clusters may be composed of several components with very different performance requirements. The FlowVR middleware allow the developer to deploy such applications and to define communication and synchronization schemes between components without modifying the code. Whereas it eases the creation of mappings, FlowVR does not come with a performance model. Consequently optimization of mappings is left to the developer skills. This task seems difficult to perform when the number of components and cluster nodes grow. Moreover the cluster may be composed of heterogeneous nodes making this task even more complex. In this paper we propose an approach to predict performances of FlowVR distributed applications given a mapping and a cluster. We also give some advices to the developer to create efficient mappings and avoid configurations which may lead to issues. Since the FlowVR model is very closed to underlying models of lots of distributed codes, our approach can be useful for all designers of such applications.
Mot(s) Clé(s) : Distributed applications, performance prediction, FlowVR
RR-2007-08 Task-to-processor allocation for distributed heterogeneous applications on SMP clusters
Sylvain Jubertie, Emmanuel Melin
Résumé : Today, distributed architectures are based on multi core SMP nodes. Several middleware, like the FlowVR framework, exist to design interactive and heterogeneous distributed applications for these architectures. FlowVR defines an application as a set of codes mapped on cluster nodes and linked by a communication and synchronization network. But if we control the way modules are synchronized and mapped on nodes, we do not control the scheduling of concurrent modules on processors which is done by the Operating System scheduler. Since modules may be synchronized across different nodes, each local scheduling can affect the whole application performance. Moreover the OS scheduling is dynamic thus it is very difficult to predict and guarantee performance of such applications and especially of interactive ones because performance variations may totally break the immersion feeling. In this paper we propose to use a performance model to determine the processor load required by each distributed task. With this information we can define a task-to-processor allocation and tune the scheduler to respect it. Thus we can abstract this allocation from a particular OS, avoid effects of a dynamic scheduling, guarantee performance, optimize the processor use and the number of nodes used for our application.
Mot(s) Clé(s) : distributed heterogeneous applications,process allocation, clusters
RR-2007-09 On Compatible Normal Odd Partitions in Cubic Graphs
Jean-Luc Fouquet and Jean-Marie Vanherpe
Résumé : A normal odd partition of the edges of a cubic graph is a partition into trails of odd length (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition and internal in another trail. For each vertex, we can distinguish the edge for which this vertex is pending. Three normal odd partitions are compatible whenever these distinguished edges are distinct for each vertex. We study here this notion and show that a cubic three edge-colorable graph can always be provided with three compatible normal odd partitions. The Petersen graph have this property and we can construct other cubic graphs with chromatic index four with the same property. At last, we give a connexion with the Fan Rapaud conjecture and propose a new conjecture which, if true, would imply this conjecture.
Mot(s) Clé(s) : Cubic graphs, edge partition
RR-2007-10 Relevant dimensions for classification and visualization
Lionel Martin, Matthieu Exbrayat
Résumé : In this paper we introduce a dimensionality reduction method based on object class, which can be of interest both to define an appropriate distance measure or to visualize objects in a multidimensional space. The method we present is derived from data analysis techniques, such as Principal Components Analysis (PCA). In this paper we propose to consider only pairs of objects that belong to different classes, i.e. to maximise inter-classes distance. Moreover, we introduce a weight parameter that limits the influence of distant objects and favours the influence of close ones, in order to focus on local spatial organization, and thus raise the quality of nearest neighbour classification. Various tests results are presented, which show that a small set of characteristic dimensions can be sufficient to achieve a very satisfying good classification rate.
Mot(s) Clé(s) : Réduction de dimensions, visualisation
RR-2007-11 On isomorphic linear partitions in cubic graphs
J-L. Fouquet, H. Thuillier, J-M. Vanherpe (LIFO) and A.P. Wojda (AGH University of Science and Technology, Cracovie)
Résumé : A linear forest is a graph that connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. It is well known that la(G)=2 when G is a cubic graph and Wormald conjectured that if |V(G)= 0 (mod 4), then it is always possible to find a linear partition in two isomorphic linear forests. We give here some new results concerning this conjecture.
Mot(s) Clé(s) : cubic graphs; linear-arboricity
RR-2007-12 A Clausal View for Access Control and XPath Query Evaluation
Barbara FILA, Siva ANANTHARAMAN
Résumé : We show that access control policies on semi-structured, XML-like, documents can be handled naturally by a clausal view, for positive queries in the XPath format. The evaluation of any such query Q, on any given document t, is done step-wise, under unambiguous runs of a transition graph G_Q, that we associate with any XPath query Q given in canonical form; the runs of the graph G_Q on t are defined in terms of clauses, controlled by appropriate set(s) of constraints.
Mot(s) Clé(s) : XML, XPath, query, access control, constraints, clauses
RR-2007-13 On linear arboricity of cubic graphs
Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe, Pawel Wojda
Résumé : Une foret lineaire est un graphe simple dont les composantes connexes sont des chemins sans corde. Une partition lineaire d'un graphe G est une partition de l'ensemble E(G) de ses aretes en forets lineaires et la(G) designe le nombre minimum de forets lineaires d'une partition lineaire. Lorsque chaque chemin possede une longueur au plus egale a k, une foret lineaire est appelee foret k-lineaire et la_k(G) designe le nombre minimum de forets lineaires partitionnant E(G). Il est clair que la_{n-1}(G)=la(G). Dans cet article nous considerons les forets lineaires des graphes cubiques, pour lequels on sait que la(G)=2. Nous donnons les principaux resultats connus sur ce sujet et nous posons de nouvelles conjectures.
Mot(s) Clé(s) : graphe cubique, arboricite lineaire, couplage fort
RR-2007-14 On odd and semi-odd linear partitions of cubic graphs
J-L Fouquet, H. Thuillier, J-M Vanherpe, P. Wojda
Résumé : A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G)=2. A linear partition into the linear forests L_B and L_R is said to be odd whenever each path of L_B U L_R has odd length and semi-odd whenever each path of L_B (or each path of L_R) has odd length. Aldred and Wormald showed that a cubic graph G is 3-edge colourable if and only if G has an odd linear partition. We give here more precise results and we study relationships between semi-odd linear partitions and perfect matching.
Mot(s) Clé(s) : Cubic graph, linear arboricity, perfect matching, strong matching, 3-edge colouring
RR-2007-15 A generalization of k-Means for Overlapping Clustering
Guillaume Cleuziou
Résumé : This paper deals with overlapping clustering, a trade off between crisp and fuzzy clustering. It has been motivated by recent applications in various domains such as Information Retrieval or biology. We show that the problem of finding a suitable coverage of data by overlapping clusters is not a trivial task and we propose the algorithm OKM that generalizes the k-means algorithm combining a new objective criterion coupled with an optimization heuristic. Experimental results in the context of document clustering show that OKM first generates suitables overlaps between classes and then outperforms the overlapping clusters derived from fuzzy approaches (e.g. fuzzy-k-means).
Mot(s) Clé(s) :
Les rapports de recherche du LIFO en 2007
RR-2007-01
Performance Evaluation of a Parallel Algorithm for "GroupBy-Join" Queries Processing in Distributed Architectures
M. Al Hajj Hassan et M. Bamha
Date : 2007-06-25
Résumé Télécharger
RR-2007-02
Intruders with Caps
S. Anantharaman, P. Narendran, M. Rusinowitch
Date : 2007-01-18
Résumé Télécharger
RR-2007-03
Performance Prediction for Distributed Virtual Reality Applications Mappings on PC Clusters
Sylvain Jubertie, Emmanuel Melin
Date : 2007-02-09
Résumé Télécharger
RR-2007-04
Faithful embedding on finite orders classes
Alain Guillet, Jimmy Leblet, Jean-Xavier Rampon
Date : 2007-01-29
Résumé Télécharger
RR-2007-05
Inductive Characterizations of Finite Interval Orders and
Semiorders
Jimmy Leblet, Jean-Xavier Rampon
Date : 2007-01-29
Résumé Télécharger
RR-2007-06
Towards a Resource-Safe Erlang
David Teller
Date : 2007-02-13
Résumé Télécharger
RR-2007-07
Mapping and Performance Prediction for Distributed Applications on Heterogeneous Clusters
Sylvain Jubertie, Emmanuel Melin
Date : 2007-02-19
Résumé Télécharger
RR-2007-08
Task-to-processor allocation for distributed heterogeneous applications on SMP clusters
Sylvain Jubertie, Emmanuel Melin
Date : 2007-04-05
Résumé Télécharger
RR-2007-09
On Compatible Normal Odd Partitions in Cubic Graphs
Jean-Luc Fouquet and Jean-Marie Vanherpe
Date : 2007-05-02
Résumé Télécharger
RR-2007-10
Relevant dimensions for classification and visualization
Lionel Martin, Matthieu Exbrayat
Date : 2007-05-15
Résumé Télécharger
RR-2007-11
On isomorphic linear partitions in cubic graphs
J-L. Fouquet, H. Thuillier, J-M. Vanherpe (LIFO) and A.P. Wojda (AGH University of Science and Technology, Cracovie)
Date : 2007-05-03
Résumé Télécharger
RR-2007-12
A Clausal View for Access Control and XPath Query Evaluation
Barbara FILA, Siva ANANTHARAMAN
Date : 2007-06-01
Résumé Télécharger
RR-2007-13
On linear arboricity of cubic graphs
Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe, Pawel Wojda
Date : 2007-06-11
Résumé Télécharger
RR-2007-14
On odd and semi-odd linear partitions of cubic graphs
J-L Fouquet, H. Thuillier, J-M Vanherpe, P. Wojda
Date : 2007-07-26
Résumé Télécharger
RR-2007-15
A generalization of k-Means for Overlapping Clustering
Guillaume Cleuziou
Date : 2007-07-16
Résumé Télécharger
Résumés des rapports de recherche
RR-2007-01 Performance Evaluation of a Parallel Algorithm for "GroupBy-Join" Queries Processing in Distributed Architectures
M. Al Hajj Hassan et M. Bamha
Résumé : SQL queries involving join and group-by operations are fairly common in many decision support applications where the size of the input relations is usually very large, so the parallelization of these queries is highly recommended in order to obtain a desirable response time. Several parallel algorithms that treat this kind of queries have been presented in the literature. However, their most significant drawbacks are that they are very sensitive to data skew and involve expensive communication and Input/Output costs in the evaluation of the join operation. In this paper, we present an algorithm that overcomes these drawbacks because it evaluates the "GroupBy-Join" query without the need of the direct evaluation of the costly join operation, thus reducing its Input/Output and communication costs. The performance of this algorithm is analyzed using the scalable and portable BSP (Bulk Synchronous Parallel) cost model which predicts a near optimal linear speedup even for highly skewed data. These performance predictions were also validated by the implementation results.
Mot(s) Clé(s) : PDBMS, Parallel joins, Data skew, Join product skew, GroupBy-Join queries, BSP cost model.
RR-2007-02 Intruders with Caps
S. Anantharaman, P. Narendran, M. Rusinowitch
Résumé : In the analysis of cryptographic protocols, a treacherous set of terms is one from which an intruder can get access to what was intended to be secret, by adding on to the top of a sequence of elements of this set, a cap formed of symbols legally part of his/her knowledge. In this paper, we give sufficient conditions on the rewrite system modeling the intruder's abilities, such as using encryption and decryption functions, to ensure that it is decidable if such caps exist. The following classes of intruder systems are studied: linear, dwindling, \Delta-strong, and optimally reducing; and depending on the class considered, the cap problem (``find a cap for a given set of terms'') is shown respectively to be in P, NP-complete, decidable, and undecidable.
Mot(s) Clé(s) :
RR-2007-03 Performance Prediction for Distributed Virtual Reality Applications Mappings on PC Clusters
Sylvain Jubertie, Emmanuel Melin
Résumé : Large and distributed Virtual Reality applications are often built from heterogeneous parallel codes. FlowVR offers a design model to easily compose a loosely coupled VR distributed application. FlowVR highly facilitates the development of this kind of applications making possible the description of their coupling and their mapping on the cluster nodes independently of their code. Nevertheless, the choice of a good mapping is leaved to the developer skill. In an other hand, VR applications may include lots of different components and clusters may also be composed of numerous and heterogeneous nodes and networks. In this case it seems very difficult to map efficiently a distributed VR aplication onto a large cluster without tools to help the programmer to analyse his choices. The FlowVR design, particularly does not propose any kind of performance model. In this paper we present an approach to determine performances of VR applications from a FlowVR network and from caracteristics of a cluster. We also give some advices to the developer to design efficient FlowVR mappings. Since FlowVR model is very closed to underlying models of lots of VR codes, our approach can be useful for all designers of such applications.
Mot(s) Clé(s) :
RR-2007-04 Faithful embedding on finite orders classes
Alain Guillet, Jimmy Leblet, Jean-Xavier Rampon
Résumé : Nous étudions, dans le cadres des classes d'ordres finis, la notion d'extension respectueuse pour les relations, notion introduite en 1971 par R. Fraïssé. Cette notion permet d'étudier, à travers les sous-structures interdites, les relations d'ordres d'une manière inhabituelle et met ainsi en lumière des caractéristiques structurelles spécifiques. Dans ce papier, nous montrons que, pour la plus part des classes d'ordres connues, n'importe quel ordre appartenant à cette classe admet une extension respectueuse appartenant aussi à cette classe.
Mot(s) Clé(s) : extension, extension respectueuse, isomorphisme, ordres finis, ordres partiels, plongement.
RR-2007-05 Inductive Characterizations of Finite Interval Orders and Semiorders
Jimmy Leblet, Jean-Xavier Rampon
Résumé : Nous introduissons des définitions inductives de deux classes d'ordres. Par des preuves simples, nous prouvons que l'une d'elles correspond à la classe des ordres d'intervalles finis et que l'autre est exactement la classe des semi-ordres. Pour conclure, on considère les principaux théorèmes de caractérisations de ces classes et donnons des preuves simples et directes d'équivalence avec nos caractérisations.
Mot(s) Clé(s) : antichaîne, caractérisation, décomposition, définition inductive, ordres d'intervalles, ordres finis, ordres partiels, semi-ordres.
RR-2007-06 Towards a Resource-Safe Erlang
David Teller
Résumé : Lentement mais sûrement, l'industrie découvre le besoin de langages de programmation, d'environnements d'exécution et de méthodologies adaptées au développement d'applications collaboratives et distribuées. Malheureusement, à l'heure actuelle, les plate-formes disponibles pour ces applications restent fragiles vis-à-vis d'un grand nombre de situations, en particulier les attaques d'épuisement de ressources et de Déni de Service, et ne peuvent répondre à ces attaques, au mieux, que cas par cas. Au cours de ce travail, nous avons étudié le problème de la gestion des ressources dans le langage Erlang : comment fournir des services, utilisables à travers le réseau, tout en s'assurant que des tierces-parties mal intentionnées ne pourront pas manipuler ces points d'entrée dans le système pour monopoliser l'intégralité de la mémoire vive, de la table des fichiers ou de toute autre ressource limitée et critique ? Pour contribuer à répondre à cette question, nous produisons une sémantique formelle de Core Erlang, un modèle de certaines fonctions de sa bibliothèque standard, auxquels nous associons un système de types conçu pour prouver formellement la robustesse de services vis-à-vis d'attaques de Déni de Service.
Mot(s) Clé(s) : Systèmes distribués, Attaques de Déni de Service, Algèbres de Processus, Systèmes de Types, Analyse Statique, Ressources, Erlang, pi-calcul
RR-2007-07 Mapping and Performance Prediction for Distributed Applications on Heterogeneous Clusters
Sylvain Jubertie, Emmanuel Melin
Résumé : Distributed applications running on clusters may be composed of several components with very different performance requirements. The FlowVR middleware allow the developer to deploy such applications and to define communication and synchronization schemes between components without modifying the code. Whereas it eases the creation of mappings, FlowVR does not come with a performance model. Consequently optimization of mappings is left to the developer skills. This task seems difficult to perform when the number of components and cluster nodes grow. Moreover the cluster may be composed of heterogeneous nodes making this task even more complex. In this paper we propose an approach to predict performances of FlowVR distributed applications given a mapping and a cluster. We also give some advices to the developer to create efficient mappings and avoid configurations which may lead to issues. Since the FlowVR model is very closed to underlying models of lots of distributed codes, our approach can be useful for all designers of such applications.
Mot(s) Clé(s) : Distributed applications, performance prediction, FlowVR
RR-2007-08 Task-to-processor allocation for distributed heterogeneous applications on SMP clusters
Sylvain Jubertie, Emmanuel Melin
Résumé : Today, distributed architectures are based on multi core SMP nodes. Several middleware, like the FlowVR framework, exist to design interactive and heterogeneous distributed applications for these architectures. FlowVR defines an application as a set of codes mapped on cluster nodes and linked by a communication and synchronization network. But if we control the way modules are synchronized and mapped on nodes, we do not control the scheduling of concurrent modules on processors which is done by the Operating System scheduler. Since modules may be synchronized across different nodes, each local scheduling can affect the whole application performance. Moreover the OS scheduling is dynamic thus it is very difficult to predict and guarantee performance of such applications and especially of interactive ones because performance variations may totally break the immersion feeling. In this paper we propose to use a performance model to determine the processor load required by each distributed task. With this information we can define a task-to-processor allocation and tune the scheduler to respect it. Thus we can abstract this allocation from a particular OS, avoid effects of a dynamic scheduling, guarantee performance, optimize the processor use and the number of nodes used for our application.
Mot(s) Clé(s) : distributed heterogeneous applications,process allocation, clusters
RR-2007-09 On Compatible Normal Odd Partitions in Cubic Graphs
Jean-Luc Fouquet and Jean-Marie Vanherpe
Résumé : A normal odd partition of the edges of a cubic graph is a partition into trails of odd length (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition and internal in another trail. For each vertex, we can distinguish the edge for which this vertex is pending. Three normal odd partitions are compatible whenever these distinguished edges are distinct for each vertex. We study here this notion and show that a cubic three edge-colorable graph can always be provided with three compatible normal odd partitions. The Petersen graph have this property and we can construct other cubic graphs with chromatic index four with the same property. At last, we give a connexion with the Fan Rapaud conjecture and propose a new conjecture which, if true, would imply this conjecture.
Mot(s) Clé(s) : Cubic graphs, edge partition
RR-2007-10 Relevant dimensions for classification and visualization
Lionel Martin, Matthieu Exbrayat
Résumé : In this paper we introduce a dimensionality reduction method based on object class, which can be of interest both to define an appropriate distance measure or to visualize objects in a multidimensional space. The method we present is derived from data analysis techniques, such as Principal Components Analysis (PCA). In this paper we propose to consider only pairs of objects that belong to different classes, i.e. to maximise inter-classes distance. Moreover, we introduce a weight parameter that limits the influence of distant objects and favours the influence of close ones, in order to focus on local spatial organization, and thus raise the quality of nearest neighbour classification. Various tests results are presented, which show that a small set of characteristic dimensions can be sufficient to achieve a very satisfying good classification rate.
Mot(s) Clé(s) : Réduction de dimensions, visualisation
RR-2007-11 On isomorphic linear partitions in cubic graphs
J-L. Fouquet, H. Thuillier, J-M. Vanherpe (LIFO) and A.P. Wojda (AGH University of Science and Technology, Cracovie)
Résumé : A linear forest is a graph that connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. It is well known that la(G)=2 when G is a cubic graph and Wormald conjectured that if |V(G)= 0 (mod 4), then it is always possible to find a linear partition in two isomorphic linear forests. We give here some new results concerning this conjecture.
Mot(s) Clé(s) : cubic graphs; linear-arboricity
RR-2007-12 A Clausal View for Access Control and XPath Query Evaluation
Barbara FILA, Siva ANANTHARAMAN
Résumé : We show that access control policies on semi-structured, XML-like, documents can be handled naturally by a clausal view, for positive queries in the XPath format. The evaluation of any such query Q, on any given document t, is done step-wise, under unambiguous runs of a transition graph G_Q, that we associate with any XPath query Q given in canonical form; the runs of the graph G_Q on t are defined in terms of clauses, controlled by appropriate set(s) of constraints.
Mot(s) Clé(s) : XML, XPath, query, access control, constraints, clauses
RR-2007-13 On linear arboricity of cubic graphs
Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe, Pawel Wojda
Résumé : Une foret lineaire est un graphe simple dont les composantes connexes sont des chemins sans corde. Une partition lineaire d'un graphe G est une partition de l'ensemble E(G) de ses aretes en forets lineaires et la(G) designe le nombre minimum de forets lineaires d'une partition lineaire. Lorsque chaque chemin possede une longueur au plus egale a k, une foret lineaire est appelee foret k-lineaire et la_k(G) designe le nombre minimum de forets lineaires partitionnant E(G). Il est clair que la_{n-1}(G)=la(G). Dans cet article nous considerons les forets lineaires des graphes cubiques, pour lequels on sait que la(G)=2. Nous donnons les principaux resultats connus sur ce sujet et nous posons de nouvelles conjectures.
Mot(s) Clé(s) : graphe cubique, arboricite lineaire, couplage fort
RR-2007-14 On odd and semi-odd linear partitions of cubic graphs
J-L Fouquet, H. Thuillier, J-M Vanherpe, P. Wojda
Résumé : A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G)=2. A linear partition into the linear forests L_B and L_R is said to be odd whenever each path of L_B U L_R has odd length and semi-odd whenever each path of L_B (or each path of L_R) has odd length. Aldred and Wormald showed that a cubic graph G is 3-edge colourable if and only if G has an odd linear partition. We give here more precise results and we study relationships between semi-odd linear partitions and perfect matching.
Mot(s) Clé(s) : Cubic graph, linear arboricity, perfect matching, strong matching, 3-edge colouring
RR-2007-15 A generalization of k-Means for Overlapping Clustering
Guillaume Cleuziou
Résumé : This paper deals with overlapping clustering, a trade off between crisp and fuzzy clustering. It has been motivated by recent applications in various domains such as Information Retrieval or biology. We show that the problem of finding a suitable coverage of data by overlapping clusters is not a trivial task and we propose the algorithm OKM that generalizes the k-means algorithm combining a new objective criterion coupled with an optimization heuristic. Experimental results in the context of document clustering show that OKM first generates suitables overlaps between classes and then outperforms the overlapping clusters derived from fuzzy approaches (e.g. fuzzy-k-means).
Mot(s) Clé(s) :
Université d'Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 