How to Match in Modern Computational Settings

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The EPFL Graph Platform is an open-source data infrastructure designed for academic institutions. It organizes educational and institutional data into a semantically interconnected knowledge graph, making it accessible through a graph-based search engine a ...

This thesis is concerned with improving the interpretability of network summaries in both a theoretical and an applied framework, with an application to clinically relevant problems in neuroscience. The theoretical part of this thesis is concerned with gra ...

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree Δcan be edge colored (offline) using no more than Γ+1 colors (with Δbeing a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL'92) conject ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

We study the fixed points of outer-totalistic cellular automata on sparse random regular graphs. These can be seen as constraint satisfaction problems, where each variable must adhere to the same local constraint, which depends solely on its state and the ...

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...

Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

Various forms of real-world data, such as social, financial, and biological networks, can be represented using graphs. An efficient method of analysing this type of data is to extract subgraph patterns, such as cliques, cycles, and motifs, from graphs. For ...

We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Cycles are one of the fundamental subgraph patterns and being able to enumerate them in graphs enables important applications in a wide variety of fields, including finance, biology, chemistry, and network science. However, to enable cycle enumeration in r ...

Wearable devices for health monitoring are essential for tracking individuals' health status and facilitating early detection of diseases. However, processing biomedical signals online for real-time monitoring is challenging due to limited computational re ...

A graph H is a minor of a second graph G if G can be transformed into H by two operations: 1) deleting nodes and/or edges, or 2) contracting edges. Coarse-grained reconfigurable array (CGRA) application mapping is closely related to the graph minor problem ...

In this paper, we study the problem of learning Graph Neural Networks (GNNs) with Differential Privacy (DP). We propose a novel differentially private GNN based on Aggregation Perturbation (GAP), which adds stochastic noise to the GNN's aggregation functio ...

In this thesis we design online combinatorial optimization algorithms for beyond worst-case analysis settings. In the first part, we discuss the online matching problem and prove that, in the edge arrival model, no online algorithm can achieve a competiti ...

This work introduces DiGress, a discrete denoising diffusion model for generating graphs with categorical node and edge attributes. Our model utilizes a discrete diffusion process that progressively edits graphs with noise, through the process of adding or ...

How to Match in Modern Computational Settings

Chat with Graph Search

GraphOntology Dataset

Nonparametric network summaries

Online Edge Coloring Is (Nearly) as Easy as Offline

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Counting and hardness-of-finding fixed points in cellular automata on random graphs

A ride time-oriented scheduling algorithm for dial-a-ride problems

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Acceleration of graph pattern mining and applications to financial crime

A Distributed Augmenting Path Approach for the Bottleneck Assignment Problem

Maximum Independent Set: Self-Training through Dynamic Programming

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-constrained Cycles

ACE: Automated optimization towards iterative Classification in Edge health monitors

GRAMM: Fast CGRA Application Mapping Based on A Heuristic for Finding Graph Minors

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

Beyond worst-case analysis, with or without predictions

DiGress: Discrete Denoising diffusion for graph generation