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.
Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer k ≥ 2 and arbitrary small ε > 0, the Feedback Vertex Set problem and the DAG Vertex Deletion problem ...
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leadi ...
A tangle is a graph drawn in the plane so that any pair of edges have precisely one point in common, and this point is either an endpoint or a point of tangency. If we allow a third option: the common point may be a proper crossing between the two edges, t ...
The prevalence of signals on weighted graphs is increasing; however, because of the irregular structure of weighted graphs, classical signal processing techniques cannot be directly applied to signals on graphs. In this paper, we define generalized transla ...
This thesis is devoted to crossing patterns of edges in topological graphs. We consider the following four problems: A thrackle is a graph drawn in the plane such that every pair of edges meet exactly once: either at a common endpoint or in a proper crossi ...
We study the time complexity for deterministic broadcasting algorithms in mobile radio networks. The broadcast operation consists of a source node successfully communicating its message to every other node. In multi-hop radio networks such as MANETs, the m ...
A model called the linear transform network (LTN) is proposed to analyze the compression and estimation of correlated signals transmitted over directed acyclic graphs (DAGs). An LTN is a DAG network with multiple source and receiver nodes. Source nodes tra ...
Institute of Electrical and Electronics Engineers2012
The substrate scope of the [2+2] cycloaddn.-cycloreversion (CA-CR) reaction between electron-deficient (2,2-dicyanovinyl)benzene (DCVB) or (1,2,2-tricyanovinyl)benzene (TCVB) derivs. and N,N-dimethylanilino (DMA)-substituted acetylenes was studied. The str ...
We introduce an incremental cooperation mode into the framework of adaptive networks (AN). The method applies to generic topologies and avoids the need to establish a Hamiltonian cycle over the network, generalizing the original incremental mode, while kee ...
The prevalence of signals on weighted graphs is increasing; however, because of the irregular structure of weighted graphs, classical signal processing techniques cannot be directly applied to signals on graphs. In this paper, we define generalized transla ...
