Skip to Main content Skip to Navigation

Génération et tracé de structures décomposables

Abstract : The main goal of the thesis is to conceive algorithms and tools to assist people who study a special kind of combinatorial structures, namely decomposable structures. The two major questions we try to solve are: How to generate, randomly or by some systematic procedure, a decomposable structure; How to draw decomposable structures. Decornposable structures are combinatorial structures that are recursively described using a small set of constructors. The idea consists in considering a structure as a process of construction from simpler structures. The main interest of the decomposable structure theory is that we can describe an infinite number of different sets of structures, including permutations, varions kind of trees or functional graphs, for which we can solve counting and random generation problems. Possible applications are the average case analysis of algorithms and the production of test inputs for the experimental validation of programs. We propose an algorithm for drawing decomposable structures based on the translation into special graphs, that we call composed graphs, in which bath inclusion and adjacency relationships can exist. The principle is based on the translation of decomposable structures into composed graphs, i.e. graphs with both inclusion and adjacency relationships. The drawing of composed graph is achieved by using different classical graph drawing algorithm together. The number of algorithms that can be used on a sarne drawing is infinite. The only restriction is that the algorithms must be able to draw graphs with arbitrary node sizes. We present two graph drawing software realisations that we wrote in order to validate the algorithms presented in the thesis. They can be linked to combinatorial structure generation programs in order to form integrated systems. We also investigate their use for the visualisation of large data structures.
Document type :
Complete list of metadata
Contributor : Thèses UL Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 10:59:54 AM
Last modification on : Thursday, February 11, 2021 - 1:02:10 PM

Links full text


  • HAL Id : tel-01747435, version 1



François Bertault. Génération et tracé de structures décomposables. Autre [cs.OH]. Université Henri Poincaré - Nancy 1, 1997. Français. ⟨NNT : 1997NAN10297⟩. ⟨tel-01747435⟩



Record views