- Contacts/Reaching LIFO
- Teaching
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
Go to Research Reports of Year : 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
Abstract : 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.
Keywords : 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
Abstract : 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.
Keywords :
RR-2007-03 Performance Prediction for Distributed Virtual Reality Applications Mappings on PC Clusters
Sylvain Jubertie, Emmanuel Melin
Abstract : 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.
Keywords :
RR-2007-04 Faithful embedding on finite orders classes
Alain Guillet, Jimmy Leblet, Jean-Xavier Rampon
Abstract : We investigate, in the particular case of finite orders classes, the notion of faithful embedding among relations introduced in 1971 by R. Fraïssé. This notion leads to the study, by forbidden substructures, of orders relations in a way which isn't the usual one and thus point out specific structural characteristics. In this paper we show that, for most of the known classes of orders, any order belonging to such a class admits a faithful embedding also belonging to this class.
Keywords : embedding, extension, faithful embedding, finite orders, isomorphism, partially ordered set, poset.
RR-2007-05 Inductive Characterizations of Finite Interval Orders and Semiorders
Jimmy Leblet, Jean-Xavier Rampon
Abstract : We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval orders class and that the other is exactly the semiorders class. To conclude we consider most of the known equivalence theorems on interval orders and on semiorders, and we give simple and direct inductive proofs of these equivalences with ours characterizations.
Keywords : antichain, characterization, decomposition, finite order, inductive definition, interval order, partially ordered sets, semiorder.
RR-2007-06 Towards a Resource-Safe Erlang
David Teller
Abstract : Slowly but surely, industry is discovering the need for programming languages, runtime environments and methodologies adapted to collaborative and distributed computing platforms. However, current distributed platforms, whether industrial or academic, are generally fragile with respect to resource exhaustion, and can provide, at best, ad hoc solutions to counter accidents or Denial of Service attacks. In this report, we examine the problem of resource management in Erlang, that is providing services for distant use, while ensuring that untrusted third-parties using the services may not cause the exhaustion of memory, file handles or other limited resources. For this, we provide a formal semantics for a subset of Core Erlang, as well as a model of fragments of its library, and we provide a type system for formally proving robustness of services with respect to Denial of Service attacks.
Keywords : Distributed Systems, Denial of Service, Process Algebras, Type Systems, Static Analysis, Resources, Erlang, pi-calculus
RR-2007-07 Mapping and Performance Prediction for Distributed Applications on Heterogeneous Clusters
Sylvain Jubertie, Emmanuel Melin
Abstract : 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.
Keywords : Distributed applications, performance prediction, FlowVR
RR-2007-08 Task-to-processor allocation for distributed heterogeneous applications on SMP clusters
Sylvain Jubertie, Emmanuel Melin
Abstract : 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.
Keywords : distributed heterogeneous applications,process allocation, clusters
RR-2007-09 On Compatible Normal Odd Partitions in Cubic Graphs
Jean-Luc Fouquet and Jean-Marie Vanherpe
Abstract : 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.
Keywords : Cubic graphs, edge partition
RR-2007-10 Relevant dimensions for classification and visualization
Lionel Martin, Matthieu Exbrayat
Abstract : 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.
Keywords : dimensionality reduction, visualization
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)
Abstract : 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.
Keywords : cubic graphs; linear-arboricity
RR-2007-12 A Clausal View for Access Control and XPath Query Evaluation
Barbara FILA, Siva ANANTHARAMAN
Abstract : 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.
Keywords : 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
Abstract : A linear forest is a graph in which each connected component is a chordless path. A linear partition of a graph G is a partition of its edge set E(G) into linear forests and la(G) is the minimum number of linear forests in a linear partition. When each path has length at most k a linear forest is a linear k-forest and la_k(G) will denote the minimum number of linear k-forests partitioning E(G). We clearly have la_{n-1}(G)=la(G). In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G)=2. We give a survey of already known results with new ones and new conjectures
Keywords : cubic graph, linear arboricity, strong matching
RR-2007-14 On odd and semi-odd linear partitions of cubic graphs
J-L Fouquet, H. Thuillier, J-M Vanherpe, P. Wojda
Abstract : 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.
Keywords : Cubic graph, linear arboricity, perfect matching, strong matching, 3-edge colouring
RR-2007-15 A generalization of k-Means for Overlapping Clustering
Guillaume Cleuziou
Abstract : 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).
Keywords :
LIFO Research Report for Year 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
Abstract Download
RR-2007-02
Intruders with Caps
S. Anantharaman, P. Narendran, M. Rusinowitch
Date : 2007-01-18
Abstract Download
RR-2007-03
Performance Prediction for Distributed Virtual Reality Applications Mappings on PC Clusters
Sylvain Jubertie, Emmanuel Melin
Date : 2007-02-09
Abstract Download
RR-2007-04
Faithful embedding on finite orders classes
Alain Guillet, Jimmy Leblet, Jean-Xavier Rampon
Date : 2007-01-29
Abstract Download
RR-2007-05
Inductive Characterizations of Finite Interval Orders and
Semiorders
Jimmy Leblet, Jean-Xavier Rampon
Date : 2007-01-29
Abstract Download
RR-2007-06
Towards a Resource-Safe Erlang
David Teller
Date : 2007-02-13
Abstract Download
RR-2007-07
Mapping and Performance Prediction for Distributed Applications on Heterogeneous Clusters
Sylvain Jubertie, Emmanuel Melin
Date : 2007-02-19
Abstract Download
RR-2007-08
Task-to-processor allocation for distributed heterogeneous applications on SMP clusters
Sylvain Jubertie, Emmanuel Melin
Date : 2007-04-05
Abstract Download
RR-2007-09
On Compatible Normal Odd Partitions in Cubic Graphs
Jean-Luc Fouquet and Jean-Marie Vanherpe
Date : 2007-05-02
Abstract Download
RR-2007-10
Relevant dimensions for classification and visualization
Lionel Martin, Matthieu Exbrayat
Date : 2007-05-15
Abstract Download
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
Abstract Download
RR-2007-12
A Clausal View for Access Control and XPath Query Evaluation
Barbara FILA, Siva ANANTHARAMAN
Date : 2007-06-01
Abstract Download
RR-2007-13
On linear arboricity of cubic graphs
Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe, Pawel Wojda
Date : 2007-06-11
Abstract Download
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
Abstract Download
RR-2007-15
A generalization of k-Means for Overlapping Clustering
Guillaume Cleuziou
Date : 2007-07-16
Abstract Download
Abstracts of Research Reports
RR-2007-01 Performance Evaluation of a Parallel Algorithm for "GroupBy-Join" Queries Processing in Distributed Architectures
M. Al Hajj Hassan et M. Bamha
Abstract : 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.
Keywords : 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
Abstract : 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.
Keywords :
RR-2007-03 Performance Prediction for Distributed Virtual Reality Applications Mappings on PC Clusters
Sylvain Jubertie, Emmanuel Melin
Abstract : 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.
Keywords :
RR-2007-04 Faithful embedding on finite orders classes
Alain Guillet, Jimmy Leblet, Jean-Xavier Rampon
Abstract : We investigate, in the particular case of finite orders classes, the notion of faithful embedding among relations introduced in 1971 by R. Fraïssé. This notion leads to the study, by forbidden substructures, of orders relations in a way which isn't the usual one and thus point out specific structural characteristics. In this paper we show that, for most of the known classes of orders, any order belonging to such a class admits a faithful embedding also belonging to this class.
Keywords : embedding, extension, faithful embedding, finite orders, isomorphism, partially ordered set, poset.
RR-2007-05 Inductive Characterizations of Finite Interval Orders and Semiorders
Jimmy Leblet, Jean-Xavier Rampon
Abstract : We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval orders class and that the other is exactly the semiorders class. To conclude we consider most of the known equivalence theorems on interval orders and on semiorders, and we give simple and direct inductive proofs of these equivalences with ours characterizations.
Keywords : antichain, characterization, decomposition, finite order, inductive definition, interval order, partially ordered sets, semiorder.
RR-2007-06 Towards a Resource-Safe Erlang
David Teller
Abstract : Slowly but surely, industry is discovering the need for programming languages, runtime environments and methodologies adapted to collaborative and distributed computing platforms. However, current distributed platforms, whether industrial or academic, are generally fragile with respect to resource exhaustion, and can provide, at best, ad hoc solutions to counter accidents or Denial of Service attacks. In this report, we examine the problem of resource management in Erlang, that is providing services for distant use, while ensuring that untrusted third-parties using the services may not cause the exhaustion of memory, file handles or other limited resources. For this, we provide a formal semantics for a subset of Core Erlang, as well as a model of fragments of its library, and we provide a type system for formally proving robustness of services with respect to Denial of Service attacks.
Keywords : Distributed Systems, Denial of Service, Process Algebras, Type Systems, Static Analysis, Resources, Erlang, pi-calculus
RR-2007-07 Mapping and Performance Prediction for Distributed Applications on Heterogeneous Clusters
Sylvain Jubertie, Emmanuel Melin
Abstract : 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.
Keywords : Distributed applications, performance prediction, FlowVR
RR-2007-08 Task-to-processor allocation for distributed heterogeneous applications on SMP clusters
Sylvain Jubertie, Emmanuel Melin
Abstract : 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.
Keywords : distributed heterogeneous applications,process allocation, clusters
RR-2007-09 On Compatible Normal Odd Partitions in Cubic Graphs
Jean-Luc Fouquet and Jean-Marie Vanherpe
Abstract : 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.
Keywords : Cubic graphs, edge partition
RR-2007-10 Relevant dimensions for classification and visualization
Lionel Martin, Matthieu Exbrayat
Abstract : 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.
Keywords : dimensionality reduction, visualization
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)
Abstract : 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.
Keywords : cubic graphs; linear-arboricity
RR-2007-12 A Clausal View for Access Control and XPath Query Evaluation
Barbara FILA, Siva ANANTHARAMAN
Abstract : 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.
Keywords : 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
Abstract : A linear forest is a graph in which each connected component is a chordless path. A linear partition of a graph G is a partition of its edge set E(G) into linear forests and la(G) is the minimum number of linear forests in a linear partition. When each path has length at most k a linear forest is a linear k-forest and la_k(G) will denote the minimum number of linear k-forests partitioning E(G). We clearly have la_{n-1}(G)=la(G). In this paper we consider linear partitions of cubic simple graphs for which it is well known that la(G)=2. We give a survey of already known results with new ones and new conjectures
Keywords : cubic graph, linear arboricity, strong matching
RR-2007-14 On odd and semi-odd linear partitions of cubic graphs
J-L Fouquet, H. Thuillier, J-M Vanherpe, P. Wojda
Abstract : 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.
Keywords : Cubic graph, linear arboricity, perfect matching, strong matching, 3-edge colouring
RR-2007-15 A generalization of k-Means for Overlapping Clustering
Guillaume Cleuziou
Abstract : 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).
Keywords :
University of Orléans | INSA Centre Val de Loire
LIFO - Laboratoire d'Informatique Fondamentale d'Orléans 