Publication

On Broadcast with a Common Message over Networks

Related publications (48)

Graph Chatbot

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.

Diameter Graphs in R-4

Andrei Kupavskii

A diameter graph in is a graph whose set of vertices is a finite subset of and whose set of edges is formed by pairs of vertices that are at diameter apart. This paper is devoted to the study of different extremal properties of diameter graphs in and on a ...

Springer2014

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...

IEEE2013

Hardness of Vertex Deletion and Project Scheduling

Ola Nils Anders Svensson

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

Springer2012

Reduced-Dimension Linear Transform Coding of Correlated Signals in Networks

Michael Christoph Gastpar, Naveen Goela

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

Lower bounds on the obstacle number of graphs

János Pach, Doemoetoer Palvoelgyi, Padmini Mukkamala

Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be con ...

2012

Location System and Corresponding Calibration Method

Pierre-André Farine, Cyril Botteron, Phillip Tomé

The present invention relates to a location system, for locating at least one object within a predefined cell, comprising at least first and second receivers (A, B, C, D), first and second transmitters respectively, including first and second internal cloc ...

2012

Bilinear Control Systems with Forced Integrable Filtration

Philippe Müllhaupt, Basile Graf

A class of nonlinear systems and a filtration of the corresponding codistributions are presented. The filtration enjoys some strong integrability property which allows an easy computation of a linearizing normal form whenever the algorithm terminates with ...

American Institute of Physics2012

The impact of mobility on the time complexity for deterministic broadcasting in radio networks

André Schiper, David Cavin, Yoav Sasson

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

2011

Degraded two-message multicast over graphs

Christina Fragouli, Shirin Saeedi Bidokhti

We consider communication of two degraded mes- sage sets over graphs where a common source sends two prioritized messages (a common and a private message) to several receivers. All receivers require the common message and a subset of the receivers require ...

2011

Drawing Hamiltonian cycles with no large angles

János Pach

Let n >= 4 be even. It is shown that every set S of n points in the plane can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of n straight-line edges such that the angle between any two consecutive edges is at m ...

Springer-Verlag2010