INRIA project-team GANG

Thematic team Theory and algorithmics of graphs

## Graphs

#### Day, hour and place

Tuesday at 2pm, room 1007

#### Contact(s)

#### Future talks

Graphes

mardi 20 février 2018, 14h00, Salle 1007

**Jan Arne Telle** (University of Bergen) *Width parameters of graphs and structured graph classes*

Tree-width and clique-width are well-known graph parameters of algorithmic use. Clique-width is a stronger parameter in the sense that it is bounded on more classes of graphs. In this talk we will present an even stronger graph parameter called mim-width (maximum induced matching-width). Several nicely structured graphs, like interval graphs, permutation graphs and leaf power graphs, have mim-width 1. Given a decomposition of bounded mim-width of a graph G we can solve many interesting problems on G in polynomial time. We will mention also a yet stronger parameter, sim-width (special induced matching-width), of value 1 even for chordal and co-comparability graphs.

Parts of the talk are based on joint work with O.Kwon and L.Jaffke, to appear at STACS 2018.

Graphes

mardi 13 mars 2018, 14h00, Salle 1007

**Mamadou Kante** (ISIMA) *TBA*

Graphes

mardi 27 mars 2018, 14h00, Salle 1007

**Matej Stehlik** (Université Grenoble Alpes - GSCOP) *TBA*

Graphes

mardi 03 avril 2018, 14h00, Salle 1007

**Marcin Kaminski** () *–*

#### Past talks

Graphes

lundi 12 février 2018, 14h00, Salle 3052

**Nabil Mustafa** (ESIEE) *Local Search for Geometric Optimization Problems.*

Local-search is an intuitive approach towards solving combinatorial optimization problems: start with any feasible solution, and try to improve it by local improvements. Like other greedy approaches, it can fail to find the global optimum by getting stuck on a locally optimal solution. In this talk I will present the ideas and techniques behind the use of local-search in the design of provably good approximation algorithms for some combinatorial problems, such as independent sets, vertex cover, dominating sets in geometric intersection graphs. The key unifying theme is the analysis of local expansion in planar graphs. Joint work with Norbert Bus, Shashwat Garg, Bruno Jartoux and Saurabh Ray.

Graphes

mardi 12 décembre 2017, 14h00, Salle 3052

**Jean Krivine** (IRIF) *Incremental Update for Graph Rewriting*

Graph rewriting formalisms are well-established models for the representation of biological systems such as protein-protein interaction networks. The combinatorial complexity of these models usually prevents any explicit representation of the variables of the system, and one has to rely on stochastic simulations in order to sample the possible trajectories of the underlying Markov chain. The bottleneck of stochastic simulation algorithms is the update of the propensity function that describes the probability that a given rule is to be applied next. In this talk we present an algorithm based on a data structure, called extension basis, that can be used to update the counts of predefined graph observables after a rule of the model has been applied.

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg

Graphes

mardi 17 octobre 2017, 14h00, Salle 3052

**Claire Mathieu** (DI - ENS) *Online k-compaction*

Given, at each time t = 1, 2, …, n, a new file of length l(t) and a read rate r(t), an online k-compaction algorithm must maintain a collection of at most k files, choosing (at each time t, without knowing future inputs) some of the files to merge into one, thereby incurring a merge cost equal to the total length of the merged files and a read cost equal to the read rate r(t) times the number of files present at time t. The goal is to minimize the total cost over time. K-compaction algorithms are a key component of log-structured merge trees, the file-based data structure underlying NoSQL databases such as Accumulo, Bigtable, Cassandra, HBase,and others. We initiate the theoretical study of k-compaction algorithms. We formalize the problem, consider worst-case, average-case and competitive analysis (per-instance optimality), and propose new algorithms that are optimal according to these metrics.

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.

#### Former seminar