Tag: graphs

Decision-Theoretic Approaches in Learning-Augmented Algorithms

-- Georgii Melidi (LIP6)

summary: We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, as well as stochastic measures that ...

Packing many dominating sets in a graph

-- Hossein Zaredehabadi (LISN)

summary: Given a graph G, a dominating set of G is a subset of vertices S such that every vertex not in S is adjacent to at least one vertex in S. While classical studies focus on finding the smallest dominating set of G, our focus shifts to finding the ...

Faster diameter computation in graphs of bounded Euler genus

-- Giannos Stamoulis (CNRS, IRIF)

Roditty and Vassilevska-Williams [STOC 2013] showed that computing the diameter, i.e., farthest distance between any two vertices, of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Strong Exponential Time Hypothesis fails. In a breakthrough work, Cabello [TALG 2019] showed a subquadratic algorithm in planar graphs ...

Proper conflict-free colourings of graphs

-- Quentin Chuet (LISN, GALaC)

summary: Given a graph \(G\) of maximum degree \(\Delta\), the proper colouring problem asks for the minimum number of colours that can be assigned to the vertices of \(G\) such that no pair of adjacent vertices are given the same colour; it is easy to show that at most \(\Delta ...

On the complexity of computing tree-partitions

-- Hugo Jacob (LaBRI)

summary: Tree-partitions are graph decompositions that correspond to mapping vertices to nodes of a tree in such a way that adjacent vertices in the graph are either mapped to adjacent nodes of the tree or to the same node. The width of a tree-partition is the maximum number of vertices ...

On the Structure of Potential Counterexamples to the Borodin-Kostochka Conjecture

-- Jonathan Narboni (LaBRI)

summary: The Borodin-Kostochka conjecture, a long-standing problem in graph theory, asserts that every graph \(G\) with maximum degree \(\Delta \geq 9\) satisfies \(\chi(G) \leq max \{\Delta - 1, \omega(G)\}\) where \(\chi(G)\) and \(\omega(G)\) are respectively the chromatic number and the clique number of \(G\). While the conjecture ...

Excluding a rectangular grid

-- Clément Rambaud (Université Côte d'Azur)

summary: For every positive integer k, we define the k-treedepth as the largest graph parameter td_k satisfying (i) td_k(∅)=0; (ii) td_k(G) <= 1+ td_k(G-u) for every graph G and every vertex u; and (iii) if G is a (

Eliminating more than vertices in graphs

-- Thomas Delépine (Université Paris-Saclay)

summary: Considérons le jeu suivant sur un graphe. À chaque tour, le joueur peut enlever un sommet de chaque composante connexe du graphe courant. Le but du jeu est d’éliminer tous les sommets du graphe. Le nombre minimum de tours nécessaires est appelé la treedepth du graphe. C’est ...

Reconstruction de graphes via des requêtes sur les triplets

-- Raphaëlle Maistre (Université Paris-Saclay)

summary: Considérons un oracle disposant d'un graphe labellisé caché. L'objectif de la reconstruction de graphes est de retrouver ce graphe caché en interrogeant l'oracle avec certains types de requêtes. Les requêtes que nous examinons portent sur des triplets de sommets du graphe, plus précisément, sur la structure ...

Fractional domatic number and minimum degree

-- Hugo Demaret (IPP)

summary: We present a study of a graph parameter in graph theory, named the fractional domatic number. A dominating set in a graph is a set of vertices such that every vertex outside the set is adjacent to a vertex in the set. The domatic number of a graph is ...

Page 1 / 5 »