AlGCo : algorithmique, graphes et combinatoire
Séminaire/Groupe de Travail
Département
Informatique - LIRMM
Archives année 2009-2010 |
Organisateurs : Emeric Gioan, Alexandre Pinlou, Jean Daligault |
Retour à la page d'accueil du séminaire
Sommaire
8 juillet
                           
Flavia Bonomo
(Université de Bueno Aires, Argentine)
Some new results on the b-coloring problem
This is a mix of joint works with C. Betancur, S. Choudum, G. Duran, T. Karthick, I. Koch, M. Kouider, F. Maffray, J. Marenco and M. Valencia-Pabon.
A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G is the maximum number t such
that G admits a b-coloring with t colors.
Several problems related to b-coloring of graphs have been introduced in the literature. Recently, the theory of b-colorings of graphs has been applied in to some clustering problems in data mining processes. In fact, clustering is generally defined as an unsupervised data mining process which aims to divide a set of data into groups, or clusters, such that the data within the same group are similar to each other while data from different groups are dissimilar. However, additional background information (namely constraints) is available in some domains and must be considered in the clustering solutions. A b-coloring-based approach exhibits more important clustering features an enables to build a fine partition of the data set in clusters when the number of clusters is not predefined.
In this talk, we will summarize the last algorithmic and theoretical results obtained on b-coloring and the related notions of b-perfection, b-continuity and b-monotonicity within some graph classes.
24 juin
                           
Steve Chaplick
(Université de Toronto, Canada)
Characterizing the Intersection Models of Path graphs using PR-trees
A new data structure, the PR-tree, is introduced to characterize the sets of path-tree models of path graphs.
We further characterize the sets of directed path-tree models of directed path graphs with a slight modification
to the PR-tree. An algorithm is presented which constructs a PR-tree that captures the path-tree models
of a given graph. This algorithm is extended to construct the modified PR-tree which captures the directed
path-tree models of a given graph. For a given graph with $n$ vertices and $m$ edges, these algorithms
have a runtime complexity of $O(a(n+m) * n * m)$ (where $a(s)$ is the inverse of Ackermann's function arising
from Union-Find). Additionally, the size of any PR-tree which is produced by these algorithms will be
linear with respect to the graph it is produced from. These algorithms are further used to recognize path
graphs and directed path graphs. This nearly matches the best known recognition algorithms for both path
graphs and directed path graphs (each of which has a runtime complexity of $O(n*m)$).
17 juin
                           
Éric Duchêne
Etiquetages identifiants et carrés latins
Un étiquetage identifiant des sommets d'un graphe G est une coloration
impropre qui doit permettre d'identifier de manière unique les arêtes de
G selon une fonction f de codage donnée. Par exemple, dans le cas des
étiquetages gracieux, le code d'une arête f(uv) est |f(u)-f(v)|. Bien
souvent, on s'interroge sur l'existence de tels étiquetages pour que f
soit en bijection avec {1,..,|E|}. Dans cet exposé, nous évoquerons le
cas d'une coloration récente, le set coloring, où la fonction de codage
vérifie f(uv)=f(u) XOR f(v). Cette coloration a été introduite en 2009
par Hedge, et très peu de résultats sont connus à son sujet. Nous
évoquerons la résolution du problème sur des premières familles de
graphes telles que les chaines, les cycles ou les arbres binaires, et
verront comment l'utilisation des carrés latins peut nous aider à
colorier optimalement ces graphes.
10 juin
                           
27 mai
                           
Sylvia Tondato
(Universidad Nacional de La Plata - Argentina)
Optimal clique trees in subclasses of chordal graphs
A graph G is chordal if and only if it has a clique tree: a tree
T whose vertices are cliques of G and such that for every
vertex x of G, C_x, cliques of G containing x, induces a
subtree of T. DV, UV graphs are subclasses of chordal graph
and they can be characterized by clique trees. A graph is
UV if there exists T, UV-clique tree: a tree such that
every C_x induces a path in T. A graph is DV if there
exists T, DV-clique tree: a directed tree such that every
C_x induces a path in T. In this work we present a
construction of clique trees for these subclasses which have
minimum number of leaves.
20 mai
                           
Marisa Guitterez
(Universidad Nacional de La Plata - Argentina)
From Montpellier to Montpellier: the path followed by our group of Graph Theory
Some years ago, at the beginnings of our group, Professor Andre
Batdedat, from the University of Montpellier, had a strong
influence in the path taken for us. He cooperated with the first
mathematician who works on Graph Theory in Argentina, Lia
Oubina, my supervisor. He made known Lia his interest in the
study of a certain class of graphs associated with Taxonomy: it
was the class of Dually Chordal Graphs. Through this class of
graphs I had the fortune to meet Jayme Szwarcfiter and his group.
Today is my intention to tell you how this initial study
was diversifying and growing to get here, again in Montpellier,
with the study of the class of Rooted Path graphs.
In this talk we will try to give a summary to the topics that we
have studied and we are studying, giving an overview of the most
important results that we have obtained.
It could be said that our main interest is the study of certain
classes of graphs: structural properties, resolution of some
problems restricted to them, construction of special models, etc.
On the other hand, the clique operator is one of our favorite
topics, its behavior such in particular classes as in general.
The topics on which we will discuss in this talk, can be divided
into three main groups:
-
Classes of graphs defined by a property of its
cliques: Indifference, Dually Chordal, Comparability (Tree-like).
-
Clique Graphs: general operator theory for
particular classes. New characterization, complexity of its
recognition, open problems.
-
Classes of graphs defined by intersection: Loop,
Helly-circular arc, Chordal: path graphs, directed path graphs.
rooted path.
29 avril
                           
Pim van 't Hof
(Durham University)
On graph contractions and induced minors
Joint work with Marcin Kaminski, Daniël Paulusma, Dimitrios M. Thilikos and Stefan Szeider.
A graph H is a minor of a connected graph G if H can be obtained from a subgraph of G by contracting edges.
If H can be obtained from an induced subgraph of G, or from G itself, by contracting edges,
then we say that H is an induced minor or a contraction of G, respectively.
A celebrated result by Robertson and Seymour states that the problem of deciding whether G
contains a fixed graph H as a minor can be solved in polynomial time for any graph H.
For the two related problems of deciding whether G contains a fixed graph H as an induced minor or as a contraction, the complexity picture is not so clear.
The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G contains H as an induced minor.
We show that this problem is fixed parameter tractable in |V(H)| if G belongs to any nontrivial minor-closed graph class and
H is a planar graph. For a fixed graph H, the H-Contractibility problem is to decide whether a graph can be contracted to H.
So far, H has a dominating vertex in all cases known to be polynomially solvable, whereas H does not have such a vertex in all cases
known to be NP-complete. Here, we present a class of graphs H with a dominating vertex for which H-Contractibility is NP-complete.
We also present a new class of graphs H for which H-Contractibility is solvable in polynomial time.
Finally, we study the (H,v)-Contractibility problem, where v is a vertex of H.
The input of this problem is a graph G and an integer k, and the question is whether
G is H-contractible such that the "bag" of G corresponding to v contains at least k vertices. We show that this problem
is NP-complete whenever H is connected and v is not a dominating vertex of H.
8 avril
                           
Hajo Broersma
Best possible degree sequence conditions for graph properties
We discuss recent work on graphical degree sequences,
i.e., sequences of integers that correspond to the degrees of the
vertices of a graph. Historically, such degree sequences have been
used to provide sufficient conditions for graphs to have a certain
property, such as being $k$-connected or hamiltonian. For
hamiltonicity, this research has culminated in a beautiful theorem
due to Chv\'atal (1972). This theorem gives a sufficient condition
for a graphical degree sequence to be forcibly hamiltonian, i.e.,
such that every graph with this degree sequence is hamiltonian.
Moreover, the theorem is the strongest of an entire class of
theorems in the following sense: if the theorem does not guarantee
that a sequence $\pi$ is forcibly hamiltonian, then there exists a
nonhamiltonian graph with a degree sequence that majorizes $\pi$.
Kriesell solved an open problem due to Bauer et al. by establishing
similar conditions for $k$-edge connectivity for any fixed $k$. We
will introduce a general framework for such conditions and discuss
recent progress on similar sufficient conditions for a variety of
graph properties.
This is based on joint work with Bauer, van den
Heuvel, Kahl, and Schmeichel.
18 mars
                           
Shalom Eliahou
Permutations signees et theoreme des quatre couleurs
Ce travail est en commun avec Cedric Lecouvey.
L'objet de cet expose est de presenter une nouvelle reformulation algebrique du theoreme des quatre couleurs.
Etant donnees deux permutations dans le groupe symetrique Sn,
de nombreux chemins vont de l'une a l'autre dans le graphe de Cayley de Sn relatif aux transpositions elementaires.
Certains de ces chemins peuvent avoir une propriete supplementaire, appelee la signabilite.
Celle-ci s'exprime en terme d'une comparaison entre les graphes de Cayley de Sn
et du groupe hyperoctaedral Bn des permutations signees. On montrera que le theoreme des quatre couleurs
est equivalent a l'affirmation que, pour tout n>=1 et toute paire de permutations dans Sn,
il existe un chemin signable entre celles-ci.
Transparents de l'exposé
18 février
                           
Eric Fusy
Bois de Schnyder en genre supérieur
Schnyder a montré en 1989 que toute triangulation plane peut etre munie de 3 arbres
couvrants tel que chaque arete interne apparait exactement dans un arbre. Cette structure combinatoire, désormais appelée bois de Schnyder, a de nombreuses applications :
nouveau critère de planarité pour les graphes, dessin en lignes droites sur une grille, codage, et comptage bijectif
des triangulations planes. Nous proposons ici une définition des bois de Schnyder étendue au genre supérieur. Comme application nous présentons une procédure qui permet de coder les triangulations de genre g avec 4n+O(g log(n)) bits par sommet.
11 février
                           
Benjamin Lévêque
Triangle contact representations and duality
A contact representation by triangles of a graph is a set of triangles in the plane
such that two triangles intersect on at most one point, each triangle represents
a vertex of the graph and two triangles intersects if and only if their corresponding
vertices are adjacent. de Fraysseix et al. proved that every planar graph admits
a contact representation by triangles. We strengthen this in terms of a simultaneous
contact representation by triangles of a planar map and of its dual.
A primal-dual contact representation by triangles of a planar map is
a contact representation by triangles of the primal and a contact
representation by triangles of the dual such that for every edge uv,
bordering faces f and g, the intesertection between the triangles corresponding
to u and v is the same point as the intesertection between the triangles
corresponding to f and g. We prove that every 3-connected planar map admits
a primal-dual contact representation by triangles. Moreover, it can be required
that the interiors of the triangles form a tiling of the triangle corresponding
to the outer face and that each contact point is a node of exactly three triangles.
Then, these representations are in one-to-one correspondance with generalized
Schnyder woods defined by Felsner for 3-connected planar maps.
4 février
                           
Yann Strozecki
Une approche logique des matroïdes décomposables
Les matroïdes sont des objets généralisant la notion d'indépendance linéaire.
Les graphes peuvent être vus par exemple comme des matroïdes très simples. Dans cet
exposé on montre comment les idées de décomposition de graphe (tree-width, branch-width) peuvent être adaptées aux matroïdes.
Pour des matroïdes représentables (= matrices) de branch width fixée la décision de la logique monadique du second ordre est facile.
On montre ensuite comment on peut construire des classes de matroides abstraits représentés par des arbres,
afin que la logique monadique du second ordre soit également décidable en temps linéaire.
Transparents de l'exposé
28 janvier
                           
Stéphan Thomassé
Coloring dense graphs via VC-dimension
21 janvier
                           
Nicolas Bonichon
Spanners Géométriques : liens étroits entre triangulations de TD-Delaunay et demi-Thêta-graphes
(Travail réalisé en collaboration avec Cyril Gavoille, Nicolas Hanusse et David Ilcinkas)
Un s-spanner est un sous-graphe H d’un graphe G, tel que pour tout couple de sommets,
la distance dans H soit au plus s fois la distance dans G.
Les Thêta-graphes sont une famille classique de spanner du graphe Euclidien
(graphe complet sur n sommets du plan dont la longueur d'une arête est égale à la
distance Euclidienne entre ses extrémités). Nous montrons qu’un demi-Thêta-graphe avec thêta = pi/3 est un 2-spanner du graphe Euclidien.
Pour obtenir ce résultat nous étudions les liens étroits qu’il y a entre les 1/2-théta-graphes,
les surfaces orthogonales coplanaires et les triangulations de TD-Delaunay.
Nous présenterons également plusieurs résultats secondaires et généralisations possibles liés à ces correspondances.
26 novembre et 14 janvier
                           
Jean Daligault
Je ferai une synthèse de quelques exposés de la série de conférences ALGO'09+Worker'09 qui m'ont marqués.
Je parlerai d'une part d'un résultat de Marx et Razgon sur la complexité paramétrée de Multicut,
et d'autre part de résultat négatifs sur l'existence de noyaux, par Holger Dell et Moritz Mueller.
12 novembre
                           
Mickael Montassier
(LaBRI)
Décomposition de graphes peu denses.
Soit k un entier positif.
Nous montrerons que tout graphe de degré moyen maximum inférieur à 4(k+1)(k+3)/(k2+6k+6)
admet une partition des arêtes en une forêt et un sous-graphe de degré maximum au plus k.
La preuve de ce résultat fera intervenir une méthode de déchargement à caractère global.
22 octobre
                           
Derek Corneil
Dept. of Computer Science, University of Toronto
The attempt to find an application of Lexicographic Depth First Search
Lexicograph Breadth First Search (LBFS) was introduced in the mid 1970s and became very popular in the 1990s and beyond.
Much of its success was based on a 4-vertex characterization of when an ordering of the vertices of a given graph
could have been produced by an LBFS. The determination of similar 4-vertex characterizations for BFS and DFS
led to the discovery of Lexicographic Depth First Search (LDFS). Although algorithms were developed for LDFS,
applications of the new search didn't follow quickly.
Finally (in joint work with Barnaby Dalton and Michel Habib), such an application has been found.
In particular, LDFS yields a new algorithm for finding the Minimum Path Cover (MPC) of a cocomparability
graph G without calculating the bump number of a poset associated with G's complement.
This new algorithm also finds a cutset of vertices that certifies the MPC.
Futhermore, this algorithm can be applied to posets to obtain an easy minimum
bump number algorithm together with a certi?cate.
It is also shown that LBFS cannot be used to solve these problems.
1 octobre
                           
Matthias Mnich
On Feedback Vertex Sets in Tournaments
(joint work with Serge Gaspers, formerly LIRMM)
In this talk we consider tournaments $T$, which are orientations of a complete graph.
A feedback vertex set of $T$ is a subset of vertices intersecting every directed cycle of $T$.
We prove that every tournament on $n$ vertices has at most $1.6740^n$ minimal feedback vertex
sets and some tournaments have $1.5448^n$ minimal feedback vertex sets.
This improves an old result by Moon from 1971.
Transparents de l'exposé
24 septembre
                           
Joergen Bang-Jensen
(University of Southern Denmark,
Odense, Denmark)
Paths, cycles, trees and sub(di)graphs in directed graphs
We survey a number of recent results concerning paths, cycles or
strong subdigraphs of digraphs. We illustrate the richness of the topic by
a number of results and open problems in the area. The talk is based on
the second edition of the book "Digraphs: Theory, Algorithms and
Applications", Bang-Jensen and Gutin, to be published by Springer London
2009 as well as on a recent paper by Bang-Jensen and Kriesell on mixed
linkings in digraphs.
Transparents de l'exposé
|