Joanna Ochremiak

Sum-of-Squares, Counting Logics and Graph Isomorphism

Bâtiment Lavoisier, salle LAV108

Abstract: The isomorphisms between two graphs can be described by the integral solutions of a system of linear equations and inequalities. We show that the Lasserre hierarchy of increasing...[details]

27-mars-2018

Edouard Bonnet

Description :Max Clique in Disk and Ball Graphs

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: The complexity of finding a largest clique in a disk intersection graph is a notorious open question in computational geometry. A polynomial algorithm is known since 1990 for un...[details]

20-mars-2018

Eric Colin de Verdière

Approximating planar multicut

Salle de séminaire (4B05R) - Bâtiment Copernic

Let G be a graph and R a set of pairs of vertices, called pairs of terminals. A multicut is a set of edges of G whose removal disconnects each pair in R. Computing the minimum multicut is hard both...[details]

6-mars-2018

Eunjung Kim

Description :Erdos-Posa Property of Chordless Cycles and its Applications

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: A chordless cycle is a cycle of length at least 4 that has no chord. We prove that the class of all chordless cycles has the Erdos-Posa property, which re...[details]

6-févr.-2018

Christoph Dürr

Description :The triangle scheduling problem

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: We introduce a novel scheduling problem, where jobs occupy a triangular shape on the time line. This problem is motivated by scheduling jobs with different criticality levels. A me...[details]

30-janv.-2018

Rémi de Joannis de Verclos

Easily testable properties of dense graphs

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: A graph of size n is ɛ-far from having a property P if one have to add or delete at least ɛn² edges of G to have a graph satisfying P. A graph property P is testable if f...[details]

23-janv.-2018

Andrew Ryzhikov

Some generalizations of synchronization in partial and complete DFAs

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: A deterministic finite automaton (DFA) is called synchronizing if there exists a word (called a synchronizing word) sending all its states to some particul...[details]

19-déc.-2017

Laurent Viennot

Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) ⊆ V to each node u ∈ V, in such a way that for a...[details]

12-déc.-2017

Michaël Rao

Recherche exhaustive des pentagones convexes pavant le plan

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: Quand on cherche à caractériser les formes convexes pouvant paver le plan (en s’autorisant les rotations et miroirs), seul le cas des pentagones restait ouvert. De 1918...[details]

5-déc.-2017

Nicolas Trotignon

Graphs classes defined by excluding Truemper Configurations

Salle de séminaire (4B05R) - Bâtiment Copernic

Abstract: Truemper configurations are simple structures : prisms, thetas, pyramids and wheel. A prism is a graph made of two disjoint triangle that are matched by three dis...[details]

28-nov.-2017