Lifo - Laboratoire d'Informatique Fondamentale d'orléans INSA Centre Val de Loire Université d'Orléans Université d'Orléans

Lifo > LIFO Research Report for Year 1999

 Site en Français



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

LIFO Research Report for Year 1999


RR-1999-01 About the Strong Perfect Graph Conjecture on circular partitionable graphs
A. PECHER
Date : 1999-01-14
Abstract Download

RR-1999-02 Les journées LODEC de décembre 1998
S. ANANTHARAMAN, G. HAINS (éditeurs)
Date : 1999-01-06
Abstract

RR-1999-03 Un algorithme incrémental parallèle pour la maintenance des vues matérialisées
M. BAHMA, F. BENTAYEB, G. HAINS
Date : 1999-04-15
Abstract Download

RR-1999-04 Algorithmes parallèles pour DyALog
I. DEBOURGES
Date : 1999-04-19
Abstract Download

RR-1999-05 Triangulated neighbourhoods in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Date : 1999-03-02
Abstract Download

RR-1999-06 Parallélisation d'algorithmes génétiques fondée sur le modèle BSP
A. BRAUD, C. VRAIN
Date : 1999-11-29
Abstract Download

RR-1999-07 A Cost Model For Asynchronous and Structured Message Passing
E. MELIN, B. RAFFIN, X. REBEUF, B. VIROT
Date : 1999-04-12
Abstract Download

RR-1999-08 Optimisation des synchronisations par réordonnancement des blocs de base data-parallèles pour des multiprocesseurs MIMD
M. DUPRE
Date : 1999-04-02
Abstract

RR-1999-09 Cutsets in perfect and minimal imperfect graphs
I. RUSU
Date : 1999-05-03
Abstract Download

RR-1999-10 Confluence of the BS-lambda calculus
F. LOULERGUE
Date : 1999-07-22
Abstract Download

RR-1999-11 Parallel Constraint Programming over BSP Vectors
A. LALLOUET, G. HAINS
Date : 1999-06-14
Abstract Download

RR-1999-12 Loose vertices in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Date : 1999-08-25
Abstract Download

RR-1999-13 Forbidden Subgraph Decomposition
I. RUSU, J. SPINRAD
Date : 1999-09-03
Abstract Download

RR-1999-14 On pleasant vertices in graphs
J.-L. FOUQUET, F. ROUSSEL, P. RUBIO, H. THUILLIER
Date : 1999-11-22
Abstract Download


Abstracts of Research Reports


RR-1999-01 About the Strong Perfect Graph Conjecture on circular partitionable graphs
A. PECHER
Abstract : There is a construction due to Chvatal, Graham, Perold and Whitesides for making partitionable graphs with circular symetry. It is known that this construction doesn't produce any counter-example to Berge's conjecture. Grinstead conjectured that any circular partitionable graph is generated by this construction. This question is still open. Bacso, Boros, Gurvich, Maffray and Preissmann proved that every minimally imperfect graph with circular symmetry must have an odd number of vertices. Here we prove that every minimally imperfect graph with circular symmetry doesn't have two distinct maximum cliques sharing at least one half of their vertices and two distinct maximum stable sets sharing at least one half of their vertices.
Keywords : graph; circular; partitionable; perfect; tiling; line; integers

RR-1999-02 Les journées LODEC de décembre 1998
S. ANANTHARAMAN, G. HAINS (éditeurs)
Abstract :
Keywords :

RR-1999-03 Un algorithme incrémental parallèle pour la maintenance des vues matérialisées
M. BAHMA, F. BENTAYEB, G. HAINS
Abstract : The problem of maintenance of materialized views has been the object of of increased research activity recently mainly because of applications related to data warehousing. Many sequential view maintenance algorithms are developed in the literature. If the view is defined by a relational expression involving join operators, the cost of re-evaluating the view even incrementally may be unacceptable. Indeed, database management systems require ever higher performance due to the size of data sets they manipulate and the increasing complexity of queries. The join operation is generally costly because of the size of results which is generally large with respect to the base relations' sizes. The size of the result for a multi-join can grow exponentially and parallelization of this operation is highly desirable. Moreover, when views are materialized, parallelism can greatly increase processing power as necessary for view maintenance. In this paper, we present a new parallel view maintenance algorithm where views can involve multi-joins. This algorithm is composed of (1) a parallel algorithm for evaluating incrementally views based on a new parallel join algorithms by partial duplication of data and (2) a new parallel algorithm for updating effectively materialized views. These algorithms are based on a dynamic data-redistribution model for SN machines. The performances of these algorithms are analyzed using the scalable and portable BSP cost model which predicts a near-linear speedup for our algorithms.
Keywords : PDBMS (Parallel Data Base Management Systems); materialized view maintenance, parallel incremental algorithm; data-warehouse, multi-joins; partial multi-joins; data skew; dynamic load balancing

RR-1999-04 Algorithmes parallèles pour DyALog
I. DEBOURGES
Abstract : Since about ten years, Eric Villemonte de la Clergerie (INRIA) has been building a generalised syntactic analysor: DyALog. This software has undergone many evolutions since its birth. But nowadays, it has one serious weakness: response time in the case of ambiguous grammars is much too long. So, the first goal of the parallelism study we propose for DyALog is a speed-up for execution in the case of Natural Langage grammars which are strongly ambiguous. This report describes, a complete study of possible solutions we could use: 8 algorithms are finally proposed, compared using the BSP model [VALL90] [COLL96-1], to obtain a portable prevision of time costs. One of them gives good theorical results for any type of grammar (deterministic or ambiguous). Four others give good results too, in the case of Natural Langage grammars.
Keywords : Algorithms; parallelism; BSP; grammars; syntactic analysor; compiler

RR-1999-05 Triangulated neighbourhoods in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Abstract : We call a T-vertex of a graph G=(V,E) a vertex z whose neighbourhood N(z) in G induces a triangulated graph, and we show that every C4-free Berge graph either is a clique or contains at least two non-adjacent T-vertices. An easy consequence of this result is that every $C4-free Berge graph admits a T-elimination scheme, i.e. an ordering [v_1, v_2, ..., v_n] of its vertices such that v_i is a T-vertex in the subgraph induced by v_i, v_(i+1),..., v_n$ in $G$.
Keywords : lexicographic breadth-first search, triangulated graph, perfectness

RR-1999-06 Parallélisation d'algorithmes génétiques fondée sur le modèle BSP
A. BRAUD, C. VRAIN
Abstract : We are interested in the contribution of Genetic Algorithms in the field of Knowledge Discovery in Databases. These algorithms carry out a stochastic exploration of the search space; they are thus adapted to problems for which this space is large, which is particularly the case in this domain of application. Nevertheless, the process of evolution that makes a good solution for the problem at hand emerge is in general very long, which represents a significant limit for their usefulness to solve problems. Solutions were proposed to reduce the execution costs of these algorithms, but the problem remains open and we study one of these solutions, namely parallelization. After a presentation of Genetic Algorithms, we propose three parallel algorithms that do not modify the behaviour of the sequential algorithm. These algorithms are designed according to the BSP model, which makes possible to study their cost. It is calculated within the framework of a classical application to Knowledge Discovery in Databases, namely Concept Learning from examples stored in a Database. Results of this theoretical study predict a speed-up in comparison with the sequential algorithm for two of the three algorithms proposed. Moreover one of these algorithms was implemented and experiments carried out on the prototype confirm these predictions.
Keywords : Parallel Genetic Algorithms; Concept Learning from examples; Data Mining; BSP

RR-1999-07 A Cost Model For Asynchronous and Structured Message Passing
E. MELIN, B. RAFFIN, X. REBEUF, B. VIROT
Abstract : In this paper, we present a cost model taking into account properties of present time machines. This work relies on SCLchan, an asynchronous parallel execution model allowing explicit message passing. We show that it is possible to define a complexity function for SCLchan programs. It yields a symbolic date for each communication event. These dates can be ordered to compute upper bounds for the network load. In contrast to other classical approaches this cost computation can handle asynchronism in message passing and communication/computation overlap.
Keywords : Cost Model; Symbolic Date; Parallel Programming Languages; Asynchronous Execution; Structural Clock

RR-1999-08 Optimisation des synchronisations par réordonnancement des blocs de base data-parallèles pour des multiprocesseurs MIMD
M. DUPRE
Abstract : Compiling a data parallel program for a MIMD multiprocessor architecture with shared memory gives a SPMD object program executed asynchronously. Quinn Hatcher and Seevers proposed an algorithm based on data dependency analysis adding synchronizations in a basic block of the SPMD object. This algorithm don't use any scheduling. Scheduling the code leads to a number of synchronizations less or equal than the previous algorithm and can still be lowered by some SSA transformations. An algorithm that determines the useful SSA transformations and schedules the instructions between synchronization barriers is proposed.
Keywords : Compilation; Data Parallel Languages; Asynchronous Execution Model; Shared Memory; Scheduling; Synchronization

RR-1999-09 Cutsets in perfect and minimal imperfect graphs
I. RUSU
Abstract : Cutsets turned out to be interesting in perfect graph theory mainly with respect to two kind of applications. Firstly, sufficient conditions for a graph not to be minimal imperfect can be found; secondly, composition/decomposition operations may be described. In both cases, easy (from a theoretical point of view) and/or efficient (from a practical point of view) algorithms can be envisaged. Our aim here is to present the various aspects of cutsets in perfect and minimal imperfect graphs.
Keywords : Perfect graph; cutset; connectivity

RR-1999-10 Confluence of the BS-lambda calculus
F. LOULERGUE
Abstract : The BSlambda-calculus, a formal basis for functional languages expressing bulk synchronous parallel algorithms, is presented. It is then shown to be confluent.
Keywords : BSP; functional programming

RR-1999-11 Parallel Constraint Programming over BSP Vectors
A. LALLOUET, G. HAINS
Abstract :
Keywords :

RR-1999-12 Loose vertices in C4-free Berge graphs
I. PARFENOFF, F. ROUSSEL, I. RUSU
Abstract : We call loose vertex a vertex whose neighbourhood induces a P4-free graph, and we show that every C4-free Berge graph (connexe) G which is not a clique either is breakable (i.e. G or its complementary has a star-cutset) or contains at least two non-adjacent loose vertices. Consequently, every minimal imperfect C4-free graph has loose vertices.
Keywords : lexicographic breadth-first search; perfect graph; Berge graph

RR-1999-13 Forbidden Subgraph Decomposition
I. RUSU, J. SPINRAD
Abstract : We define a new form of graph decomposition, based on forbidding a fixed bipartite graph from occurring as an induced subgraph of edges which cross a partition of the vertices. We show that some natural decompositions obtained in this way (including the generalized join proposed by Hsu) are NP-complete.
Keywords : graph decomposition; totally decomposable graphs

RR-1999-14 On pleasant vertices in graphs
J.-L. FOUQUET, F. ROUSSEL, P. RUBIO, H. THUILLIER
Abstract : This paper generalizes previous works on perfectly orderable graphs by Olariu and by Hoàng and al. Chvátal defined a graph to be perfectly orderable if there exists a linear order < on its set of vertices such that no induced path abcd with edges ab, bc, cd has both a < b and d < c. Given a graph G and a vertex v in G such that G - v is perfectly orderable, we set some conditions on v for which we deduce that G is perfectly orderable. Our method allows to construct a new class of such graphs, recognizable in polynomial time, containing quasi-brittle graphs, charming graphs and some other classes of perfectly orderable graphs.
Keywords : graph ; perfectly orderable graph ; polynomial time