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.
Artificial neural networks, electronic circuits, and gene networks are some examples of systems that can be modeled as networks, that is, as collections of interconnected nodes. In this paper we introduce the concept of terminal graph (t-graph for short), w ...
The equipartition problem on an undirected graph G=(V,E), with n nodes and a system of edge weights, is to find a subset of [n/2] nodes such as the associate cut has the smallest cost. We present a polynomial algorithm to solve the equipartition problem on ...
Parity (matching theory) and connectivity (network flows) are two main branches of combinatorial optimization. In an attempt to understand better their interrelation, we study a problem where both parity and connectivity requirements are imposed. The main ...
With the rising importance of large-scale network control, the problem of actuator placement has received increasing attention. Our goal in this paper is to find a set of actuators minimizing the metric that measures the average energy consumption of the c ...
NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider t ...
This paper's focus is the following family of problems, denoted k-ECSS, where k denotes a positive integer: given a graph (V, E) and costs for each edge, find a minimum-cost subset F of E such that (V, F) is k-edge-connected. For k=1 it is the spanning tre ...
Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletio ...
