Refine my results

A new constructive heuristic driven by machine learning for the traveling salesman problem

Mele, Umberto Junior ; Gambardella, Luca Maria ; Montemanni, Roberto

In: Algorithms, 2021, vol. 14, no. 9, p. 25

Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios with several hundred vertices. The use of Candidate Lists (CLs) has been brought up to cope with the issues. A CL is defined as a subset of all the edges linked to a given vertex such that it contains mainly edges that are believed to be...

Graph neural networks : operators and architectures

Grattarola, Daniele ; Alippi, Cesare (Dir.) ; Livi, Lorenzo (Codir.)

Thèse de doctorat : Università della Svizzera italiana, 2021 ; 2021INFO014.

This thesis explores the field of graph neural networks, a class of deep learning models designed to learn representations of graphs. We organise the work into two parts. In the first part, we focus on the essential building blocks of graph neural networks. We present three novel operators for learning graph representations: one graph convolutional layer and two methods for pooling. We put...

CPG graphs : Some Structural and Hardness Results

Champseix, Nicolas ; Galby, Esther ; Munaro, Andrea ; Ries, Bernard

In: Discrete Applied Mathematics, 2021, vol. 290, p. 17-35

In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in Deniz et al. (2018). A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every...

Blocking Total Dominating Sets Via Edge Contractions

Galby, Esther ; Mann, Felix ; Ries, Bernard

In: Theoretical Computer Science, 2021, vol. 877, p. 18-35

In this paper, we study the problem of deciding whether the total domination number of a given graph Gcan be reduced using exactly one edge contraction (called1-Edge Contraction(γt)). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete complexity dichotomy for H-free graphs.

M. Kontsevich's graph complex and the Grothendieck-Teichmüller Lie algebra

Willwacher, Thomas

In: Inventiones mathematicae, 2015, vol. 200, no. 3, p. 671-760

Balanced Partitions of Trees and Applications

Feldmann, Andreas ; Foschini, Luca

In: Algorithmica, 2015, vol. 71, no. 2, p. 354-376

On the configuration LP for maximum budgeted allocation

Kalaitzis, Christos ; Ma̧dry, Aleksander ; Newman, Alantha ; Poláček, Lukáš ; Svensson, Ola

In: Mathematical Programming, 2015, vol. 154, no. 1-2, p. 427-462

Bounds for Pach's Selection Theorem and for the Minimum Solid Angle in a Simplex

Karasev, Roman ; Kynčl, Jan ; Paták, Pavel ; Patáková, Zuzana ; Tancer, Martin

In: Discrete & Computational Geometry, 2015, vol. 54, no. 3, p. 610-636

Efficient computational strategies for doubly intractable problems with applications to Bayesian social networks

Caimo, Alberto ; Mira, Antonietta

In: Statistics and Computing, 2015, vol. 25, no. 1, p. 113-125

Empty Triangles in Complete Topological Graphs

Ruiz-Vargas, Andres

In: Discrete & Computational Geometry, 2015, vol. 53, no. 4, p. 703-712