GALaC team seminar

The GALaC team seminar is organized once a month on Friday at 14:30 in the Ada Lovelace building at LRI.

Recent and up-coming seminars

Some recent results on the integer linear programming formulation for the Max-Cut problem

-- Hung Nguyen (GALAC, LRI)

Summary: Given an undirected graph G=(V,E) where the edges are weighted by an arbitrary cost vector c, a cut S in G associated with a node subset S is the edge subset of E which contains all the edges having exactly one end-node in S. The Maximum Cut ...


Maximum Independent Set in H-free graphs

-- Edouard BONNET (GALAC, LRI)

Summary: Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1 ...

Binary pattern of length greater than 14 are abelian-2-avoidable

-- Matthieu Rosenfeld (GALAC, LRI)

Summary: Two words u and v are abelian equivalent if they are permutation of each other ("aabc" and "baca" are abelian equivalent). Let w be a word and P= P1...Pn (where the Pi are the letters of P) a pattern (a word over another alphabet), we say that w ...

See all

Translations: fr