A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

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.

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 ...

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 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 ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former 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 ...

Despite the importance and pervasiveness of Wikipedia as one of the largest platforms for open knowledge, surprisingly little is known about how people navigate its content when seeking information. To bridge this gap, we present the first systematic large ...

This paper proposes high-order accurate well-balanced (WB) energy stable (ES) adaptive moving mesh finite difference schemes for the shallow water equations (SWEs) with non flat bottom topography. To enable the construction of the ES schemes on moving mesh ...

Computational models have been widely employed to study the electrical stimulation of the nervous system. Still, most applications either study fundamental mechanisms underlying stimulation, or address qualitative scientific questions. When quantitative qu ...

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

Traditional fiber scattering models, based on ray optics, are missing some important visual aspects of fiber appearance. Previous work [Xia et al. 2020] on wave scattering from ideal extrusions demonstrated that diffraction produces strong forward scatteri ...

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 ...

Background and Objective: Event-based analog-to-digital converters allow for sparse bio-signal acquisition, enabling local sub-Nyquist sampling frequency. However, aggressive event selection can cause the loss of important bio-markers, not recoverable with ...

Byte-addressable non-volatile memory (NVM) allows programs to directly access storage using memory interface without going through the expensive conventional storage stack. However, direct access to NVM makes the NVM data vulnerable to software bugs and ha ...

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 ...

This paper presents a distributed shadow dynamic consensus (DSDC) framework to address the generation company (GENCO) strategic bidding problem in the independent system operator (ISO) operation. First, each sub-group is defined according to the communicat ...

Intelligent fault diagnosis has been increasingly improved with the evolution of deep learning (DL) approaches. Recently, the emerging graph neural networks (GNNs) have also been introduced in the field of fault diagnosis with the goal to make better use o ...

Federated learning is a semi-distributed algorithm, where a server communicates with multiple dispersed clients to learn a global model. The federated architecture is not robust and is sensitive to communication and computational overloads due to its one-m ...

Chronic pain presents a tremendous personal, societal, and financial burden. Treatment options are often limited to managing symptoms as opposed to treating the causes, and the consequences of pharmacological treatments can be immensely harmful as evidence ...

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Chat with Graph Search

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

The Power of Two Matrices in Spectral Algorithms for Community Recovery

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

Results on Sparse Integer Programming and Geometric Independent Sets

Approximation Algorithms for Allocation and Network Design

Better Trees for Santa Claus

GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation

A Large-Scale Characterization of How Readers Browse Wikipedia

High-order accurate well-balanced energy stable adaptive moving mesh finite difference schemes for the shallow water equations with non-flat bottom topography

Machine-learning predictor of nerve fiber firing rate allows the automatic optimization of electrical stimulation protocols

Fairness and Explainability in Clustering Problems

A Practical Wave Optics Reflection Model for Hair and Fur

Maximum Independent Set: Self-Training through Dynamic Programming

Event-based sampled ECG morphology reconstruction through self-similarity

TENET: Memory Safe and Fault Tolerant Persistent Transactional Memory

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

Distributed Shadow Dynamic Consensus Optimization Framework for Power Market with Parameterization Bidding Strategy of GENCOs

Filter-Informed Spectral Graph Wavelet Networks for Multiscale Feature Extraction and Intelligent Fault Diagnosis

Privatized graph federated learning

A Stand-Alone Augmented Reality Intervention for Chronic Pain using Embodied Systolic Stimulation