Régis Barbanchon

Maître de conférence en Informatique
Enseignant au
Département d'Informatique et Interaction
Faculté des Sciences de Luminy
Aix-Marseille Université
Chercheur au
Laboratoire d'Informatique Fondamentale
Equipe "Algorithmique, Combinatoire et Recherche Opérationnelle"


Coordonnées
Professionnelles
Tel: 04 860 90 453
Mail: regis.barbanchon@univ-amu.fr

Adresse:
Département d'Informatique de Luminy
163 avenue de Luminy -- Case 901
13288 Marseille Cedex 9

Bureau: LIF, 2eme etage de la BU, porte C-202
Personnelles
Tel: 09 500 87 800
Mail: regis.barbanchon@free.fr

Adresse:
Résidence Valmante, Bloc E1
151 traverse de la Gouffonne
13009 Marseille

Articles

On unique graph 3-colorability and parsimonious reductions in the plane
Régis Barbanchon
TCS (Theoretical Computer Science)
Special issue "combinatorics of the discrete plane and tilings" 2004
Download file (English .ps.gz)
The minimal logically-defined NP-complete problem
Régis Barbanchon and Etienne Grandjean
STACS'04 (Symposium on Theoretical Aspect of Computer Science), Montpellier March 2004
Download file (English .ps)
Local problems, Planar Local Problems and Linear Time
Régis Barbanchon and Etienne Grandjean
CSL'02 (Computer Science Logic), Edinburgh 22-25 September 2002
Download file (English .ps)

Technical reports

On unique graph 3-colorability and parsimonious reductions in the plane
Régis Barbanchon
Technical report, Les Cahiers du GREYC 2003
Download file (English .ps.gz)
The minimal logically-defined NP-complete problem
Régis Barbanchon and Etienne Grandjean
Technical report, Les Cahiers du GREYC 2003
Download file (English .ps)
Local problems and linear time
Régis Barbanchon and Etienne Grandjean
Technical report, Les Cahiers du GREYC 2001
Download file (English .ps.gz)
The problems SAT and HAMILTON are equivalent under linear parsimonious reductions in the plane
Régis Barbanchon
Technical report, Les Cahiers du GREYC 2001
Download file (English .ps.gz)
Planar Hamiltonian Problems and Linear Parsimonious Reductions
Régis Barbanchon
Technical report, Les Cahiers du GREYC 2001
Download file (English .ps.gz)

Thèse de Doctorat

Réductions fines entre problèmes NP-complets:
Linéarité, planarité, parcimonie et minimalité logique
Régis Barbanchon
Thèse sous la direction d'Etienne Grandjean, Décembre 2003
Télécharger le fichier (Français .ps)

Mémoire de DEA

Etude de l'algorithme de Thorup:
Plus courts chemins à source fixée en temps quasi-linéaire
Régis Barbanchon
Mémoire de DEA sous la direction d'Etienne Grandjean, 1999
Télécharger le fichier (Français .ps.gz)