GALaC team at LRI, Paris-Sud
GALaC is a research group at LRI, Paris-Sud University. We are focused on graph theory, combinatorics and network distributed systems algorithmic.
(Reported to unkwown date) Programming computing media
summary: We consider computing media consisting of billions of small identical Processing Elements (PE) communicating locally in space, and with an homogeneous and isotropic distribution. Computing media can scale arbitrary in size. Thus, they represent parallel architectures whose power can grow without limit. However, programming computing media is difficult.
(Reported to unkwown date) The Bron-Kerbosch algorithm with vertex ordering is output sensitive.
summary: The Bron-Kerbosch algorithm is a well known maximal clique enumeration algorithm. So far it was unknown whether it was output sensitive or not. In this paper we partially answer this question by proving that the Bron-Kerbosch Algorithm with vertex ordering, first introduced and studied by Eppstein, Löffler and Strash ...
Efficient generation of rectangulations and elimination trees via permutation languages
In this talk we apply the Hartung-Hoang-Mütze-Williams permutation language framework to derive exhaustive generation algorithms for two further classes of combinatorial objects, as well as Hamilton paths and cycles on the corresponding polytopes: (3) different classes of rectangulations, which are subdivisions of a rectangle into smaller rectangles (see www.combos ...
Combinatorial generation via permutation languages
In this talk we present a versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations. This framework provides a unified view on many known Gray code results and allows us to prove many new ones, and it yields efficient algorithms ...
Enumération des cartes planaires à trois bords par découpage en tranches
Parmi toutes les techniques d’énumération des cartes planaires (graphes plongés sur la sphère à deux dimensions), une des approches conceptuellement les plus simples et directes consiste à découper la carte en tranches: si on dispose d’une règle canonique de découpage et que les tranches ainsi obtenues sont faciles ...