Menu Fermer

Calendrier des séminaires ALGCo à venir

Mai 2022

lun mar mer jeu ven sam dim
dimanche 1 mai
lundi 2 mai
mardi 3 mai
mercredi 4 mai
jeudi 5 mai
vendredi 6 mai
samedi 7 mai
dimanche 8 mai
lundi 9 mai
mardi 10 mai
mercredi 11 mai
jeudi 12 mai
  • 0 h 00 min – 12 h 00 min Robert Ganian, «Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts»
    Robert Ganian, «Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts»
    0 h 00 min – 12 h 00 min

    Decompositional parameters such as treewidth are commonly used to
    obtain fixed-parameter algorithms for NP-hard graph problems. For
    problems that are W[1]-hard parameterized by treewidth, a natural
    alternative would be to use a suitable analogue of treewidth that is
    based on edge cuts instead of vertex separators. While tree-cut width
    has been coined as such an analogue of treewidth for edge cuts, its
    algorithmic applications have often led to disappointing results: out
    of twelve problems where one would hope for fixed-parameter
    tractability parameterized by an edge-cut based analogue to treewidth,
    eight were shown to be W[1]-hard parameterized by tree-cut width.

    Here, we will discuss an edge-cut based analogue to treewidth called
    edge-cut width. Edge-cut width is, intuitively, based on measuring the
    density of cycles passing through a spanning tree of the graph. Its
    benefits include not only a comparatively simple definition, but
    mainly that it has interesting algorithmic properties: it can be
    computed by a fixed-parameter algorithm, and it yields fixed-parameter
    algorithms for all the aforementioned problems where tree-cut width
    failed to do so.

vendredi 13 mai
samedi 14 mai
dimanche 15 mai
lundi 16 mai
mardi 17 mai
mercredi 18 mai
jeudi 19 mai
  • 10 h 00 min – 11 h 00 min Maximilian Gorsky, «Matching Theory, Hamiltonicity, and Barnette's Conjecture»
    Maximilian Gorsky, «Matching Theory, Hamiltonicity, and Barnette's Conjecture»
    10 h 00 min – 11 h 00 min

    Barnette’s Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.

    A graph is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette’s Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. [Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs, JCTB, 1985]. These allow us to check whether a graph we generated is a brace.

    Joint work with Sebastian Wiederrecht und Raphael Steiner.

vendredi 20 mai
samedi 21 mai
dimanche 22 mai
lundi 23 mai
mardi 24 mai
mercredi 25 mai
jeudi 26 mai
vendredi 27 mai
samedi 28 mai
dimanche 29 mai
lundi 30 mai
mardi 31 mai

Juin 2022

lun mar mer jeu ven sam dim
mercredi 1 juin
jeudi 2 juin
  • 10 h 00 min – 11 h 00 min Lars Jaffke, «A logic-based algorithmic meta-theorem for mim-width»
    Lars Jaffke, «A logic-based algorithmic meta-theorem for mim-width»
    10 h 00 min – 11 h 00 min

    We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints (A&C DN for short) which extends existential MSO1 with predicates for querying neighborhoods of vertex sets and for verifying connectivity and acyclicity of vertex sets in various powers of a graph. Building upon [Bergougnoux and Kanté, ESA 2019; SIDMA 2021], we show that the model checking problem for every fixed A&C DN formula is solvable in n^O(w) time when the input graph is given together with a branch decomposition of mim-width w. Nearly all problems that are known to be solvable in polynomial time given a branch decomposition of constant mim-width can be expressed in this framework. We add several natural problems to this list, including problems asking for diverse sets of solutions.

    Our model checking algorithm is efficient whenever the given branch decomposition of the input graph has small index in terms of the d-neighborhood equivalence [Bui-Xuan, Telle, and Vatshelle, TCS 2013]. We therefore unify and extend known algorithms for tree-width, clique-width and rank-width. Our algorithm has a single-exponential dependence on these three width measures and asymptotically matches run times of the fastest known algorithms for several problems. This results in algorithms with tight run times under the Exponential Time Hypothesis (ETH) for tree-width and clique-width; the above mentioned run time for mim-width is nearly tight under the ETH for several problems as well. Our results are also tight in terms of the expressive power of the logic: we show that already slight extensions of our logic make the model checking problem para-NP-hard when parameterized by mim-width plus formula length.

    Joint work with Benjamin Bergougnoux and Jan Dreier.

vendredi 3 juin
samedi 4 juin
dimanche 5 juin
lundi 6 juin
mardi 7 juin
mercredi 8 juin
jeudi 9 juin
  • 10 h 00 min – 11 h 00 min Daniel Gonçalves, «On comparable box dimension»
    Daniel Gonçalves, «On comparable box dimension»
    10 h 00 min – 11 h 00 min
    E.3.23 Bâtiment 4 LIRMM,

    Two boxes in $\mathbb{R}^d$ are comparable if one of them is a subset
    of a translation of the other. The comparable box dimension of a graph
    $G$ is the minimum integer $d$ such that $G$ can be represented as a
    touching graph of comparable axis-aligned boxes in $\mathbb{R}^d$. We
    show that proper minor-closed classes have bounded comparable box
    dimension and explore further properties of this notion. In particular we show that graphs with bounded comparable box dimension are treewidth fragile.

    Joint work with Z. Dvořák, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt

vendredi 10 juin
samedi 11 juin
dimanche 12 juin
lundi 13 juin
mardi 14 juin
mercredi 15 juin
jeudi 16 juin
  • 10 h 00 min – 11 h 00 min Stavros Kolliopoulos, «Precedence-Constrained Covering Problems with Multiplicity Constraints»
    Stavros Kolliopoulos, «Precedence-Constrained Covering Problems with Multiplicity Constraints»
    10 h 00 min – 11 h 00 min
    Bât 4, salle du séminaire (LIRMM - RDC Entrée)

    We study the approximability of covering problems when the set of
    items chosen to satisfy the covering constraints must be a prefix of a
    given partial order. We examine the general case with multiplicity
    constraints, where item $i$ can be chosen up to $d_i$ times. For the
    basic Precedence-Constrained Knapsack problem (PCKP) we answer an open
    question of McCormick et al. and show the existence of approximation
    algorithms with strongly-polynomial bounds.

    PCKP is a special case, with a single covering constraint, of a
    Precedence-Constrained Covering Integer Program (PCCP). For a general
    PCCP where the number of covering constraints is $m \geq 1,$ we show
    that an algorithm of Pritchard and Chakrabarty for Covering Integer
    Programs can be extended to yield an $f$-approximation, where $f$ is
    the maximum number of variables with nonzero coefficients in a
    covering constraint. This is nearly-optimal under standard
    complexity-theoretic assumptions and rather surprisingly matches the
    bound known for the problem without precedence constraints.

    Joint work with Antonis Skarlatos.

vendredi 17 juin
samedi 18 juin
dimanche 19 juin
lundi 20 juin
mardi 21 juin
mercredi 22 juin
jeudi 23 juin
vendredi 24 juin
samedi 25 juin
dimanche 26 juin
lundi 27 juin
mardi 28 juin
mercredi 29 juin
jeudi 30 juin

Juillet 2022

lun mar mer jeu ven sam dim
vendredi 1 juillet
samedi 2 juillet
dimanche 3 juillet
lundi 4 juillet
mardi 5 juillet
mercredi 6 juillet
jeudi 7 juillet
vendredi 8 juillet
samedi 9 juillet
dimanche 10 juillet
lundi 11 juillet
mardi 12 juillet
mercredi 13 juillet
jeudi 14 juillet
vendredi 15 juillet
samedi 16 juillet
dimanche 17 juillet
lundi 18 juillet
mardi 19 juillet
mercredi 20 juillet
jeudi 21 juillet
vendredi 22 juillet
samedi 23 juillet
dimanche 24 juillet
lundi 25 juillet
mardi 26 juillet
mercredi 27 juillet
jeudi 28 juillet
vendredi 29 juillet
samedi 30 juillet
dimanche 31 juillet

Pas d'événements.

Août 2022

lun mar mer jeu ven sam dim
lundi 1 août
mardi 2 août
mercredi 3 août
jeudi 4 août
vendredi 5 août
samedi 6 août
dimanche 7 août
lundi 8 août
mardi 9 août
mercredi 10 août
jeudi 11 août
vendredi 12 août
samedi 13 août
dimanche 14 août
lundi 15 août
mardi 16 août
mercredi 17 août
jeudi 18 août
vendredi 19 août
samedi 20 août
dimanche 21 août
lundi 22 août
mardi 23 août
mercredi 24 août
jeudi 25 août
vendredi 26 août
samedi 27 août
dimanche 28 août
lundi 29 août
mardi 30 août
mercredi 31 août

Pas d'événements.

Septembre 2022

lun mar mer jeu ven sam dim
jeudi 1 septembre
vendredi 2 septembre
samedi 3 septembre
dimanche 4 septembre
lundi 5 septembre
mardi 6 septembre
mercredi 7 septembre
jeudi 8 septembre
vendredi 9 septembre
samedi 10 septembre
dimanche 11 septembre
lundi 12 septembre
mardi 13 septembre
mercredi 14 septembre
jeudi 15 septembre
vendredi 16 septembre
samedi 17 septembre
dimanche 18 septembre
lundi 19 septembre
mardi 20 septembre
mercredi 21 septembre
jeudi 22 septembre
vendredi 23 septembre
samedi 24 septembre
dimanche 25 septembre
lundi 26 septembre
mardi 27 septembre
mercredi 28 septembre
jeudi 29 septembre
vendredi 30 septembre

Pas d'événements.

Octobre 2022

lun mar mer jeu ven sam dim
samedi 1 octobre
dimanche 2 octobre
lundi 3 octobre
mardi 4 octobre
mercredi 5 octobre
jeudi 6 octobre
vendredi 7 octobre
samedi 8 octobre
dimanche 9 octobre
lundi 10 octobre
mardi 11 octobre
mercredi 12 octobre
jeudi 13 octobre
vendredi 14 octobre
samedi 15 octobre
dimanche 16 octobre
lundi 17 octobre
mardi 18 octobre
mercredi 19 octobre
jeudi 20 octobre
vendredi 21 octobre
samedi 22 octobre
dimanche 23 octobre
lundi 24 octobre
mardi 25 octobre
mercredi 26 octobre
jeudi 27 octobre
vendredi 28 octobre
samedi 29 octobre
dimanche 30 octobre
lundi 31 octobre

Pas d'événements.

Novembre 2022

lun mar mer jeu ven sam dim
mardi 1 novembre
mercredi 2 novembre
jeudi 3 novembre
vendredi 4 novembre
samedi 5 novembre
dimanche 6 novembre
lundi 7 novembre
mardi 8 novembre
mercredi 9 novembre
jeudi 10 novembre
vendredi 11 novembre
samedi 12 novembre
dimanche 13 novembre
lundi 14 novembre
mardi 15 novembre
mercredi 16 novembre
jeudi 17 novembre
vendredi 18 novembre
samedi 19 novembre
dimanche 20 novembre
lundi 21 novembre
mardi 22 novembre
mercredi 23 novembre
jeudi 24 novembre
vendredi 25 novembre
samedi 26 novembre
dimanche 27 novembre
lundi 28 novembre
mardi 29 novembre
mercredi 30 novembre

Pas d'événements.

Décembre 2022

lun mar mer jeu ven sam dim
jeudi 1 décembre
vendredi 2 décembre
samedi 3 décembre
dimanche 4 décembre
lundi 5 décembre
mardi 6 décembre
mercredi 7 décembre
jeudi 8 décembre
vendredi 9 décembre
samedi 10 décembre
dimanche 11 décembre
lundi 12 décembre
mardi 13 décembre
mercredi 14 décembre
jeudi 15 décembre
vendredi 16 décembre
samedi 17 décembre
dimanche 18 décembre
lundi 19 décembre
mardi 20 décembre
mercredi 21 décembre
jeudi 22 décembre
vendredi 23 décembre
samedi 24 décembre
dimanche 25 décembre
lundi 26 décembre
mardi 27 décembre
mercredi 28 décembre
jeudi 29 décembre
vendredi 30 décembre
samedi 31 décembre

Pas d'événements.

Janvier 2023

lun mar mer jeu ven sam dim
dimanche 1 janvier
lundi 2 janvier
mardi 3 janvier
mercredi 4 janvier
jeudi 5 janvier
vendredi 6 janvier
samedi 7 janvier
dimanche 8 janvier
lundi 9 janvier
mardi 10 janvier
mercredi 11 janvier
jeudi 12 janvier
vendredi 13 janvier
samedi 14 janvier
dimanche 15 janvier
lundi 16 janvier
mardi 17 janvier
mercredi 18 janvier
jeudi 19 janvier
vendredi 20 janvier
samedi 21 janvier
dimanche 22 janvier
lundi 23 janvier
mardi 24 janvier
mercredi 25 janvier
jeudi 26 janvier
vendredi 27 janvier
samedi 28 janvier
dimanche 29 janvier
lundi 30 janvier
mardi 31 janvier

Pas d'événements.

Février 2023

lun mar mer jeu ven sam dim
mercredi 1 février
jeudi 2 février
vendredi 3 février
samedi 4 février
dimanche 5 février
lundi 6 février
mardi 7 février
mercredi 8 février
jeudi 9 février
vendredi 10 février
samedi 11 février
dimanche 12 février
lundi 13 février
mardi 14 février
mercredi 15 février
jeudi 16 février
vendredi 17 février
samedi 18 février
dimanche 19 février
lundi 20 février
mardi 21 février
mercredi 22 février
jeudi 23 février
vendredi 24 février
samedi 25 février
dimanche 26 février
lundi 27 février
mardi 28 février

Pas d'événements.

Mars 2023

lun mar mer jeu ven sam dim
mercredi 1 mars
jeudi 2 mars
vendredi 3 mars
samedi 4 mars
dimanche 5 mars
lundi 6 mars
mardi 7 mars
mercredi 8 mars
jeudi 9 mars
vendredi 10 mars
samedi 11 mars
dimanche 12 mars
lundi 13 mars
mardi 14 mars
mercredi 15 mars
jeudi 16 mars
vendredi 17 mars
samedi 18 mars
dimanche 19 mars
lundi 20 mars
mardi 21 mars
mercredi 22 mars
jeudi 23 mars
vendredi 24 mars
samedi 25 mars
dimanche 26 mars
lundi 27 mars
mardi 28 mars
mercredi 29 mars
jeudi 30 mars
vendredi 31 mars

Pas d'événements.

Avril 2023

lun mar mer jeu ven sam dim
samedi 1 avril
dimanche 2 avril
lundi 3 avril
mardi 4 avril
mercredi 5 avril
jeudi 6 avril
vendredi 7 avril
samedi 8 avril
dimanche 9 avril
lundi 10 avril
mardi 11 avril
mercredi 12 avril
jeudi 13 avril
vendredi 14 avril
samedi 15 avril
dimanche 16 avril
lundi 17 avril
mardi 18 avril
mercredi 19 avril
jeudi 20 avril
vendredi 21 avril
samedi 22 avril
dimanche 23 avril
lundi 24 avril
mardi 25 avril
mercredi 26 avril
jeudi 27 avril
vendredi 28 avril
samedi 29 avril
dimanche 30 avril

Pas d'événements.