Unit

lnformation and Network Dynamics Laboratory 1

Laboratory

Related publications (195)

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.

Conway's conjecture for monotone thrackles

János Pach

A drawing of a graph in the plane is called a thrackle if every pair of edges meet precisely once, either at a common vertex or at a proper crossing. According to Conway's conjecture, every thrackle has at most as many edges as vertices. We prove this conj ...

Mathematical Association of America2011

On the Privacy of Anonymized Networks

Matthias Grossglauser, Pedram Pedarsani

The proliferation of online social networks, and the concomitant accumulation of user data, give rise to hotly debated issues of privacy, security, and control. One specific challenge is the sharing or public release of anonymized data without accidentally ...

2011

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

Jan Kyncl

A set S of n points is 2-color universal for a graph G on n vertices if for every proper 2-coloring of G and for every 2-coloring of S with the same sizes of color classes as G has, G is straight-line embeddable on S. We show that the so-called double chai ...

2011

Drawing planar graphs of bounded degree with few slopes

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

Neighbor discovery with reception status feedback to transmitters

Ramin Khalili

Neighbor discovery is essential for the process of self-organization of a wireless network, where almost all routing and medium access protocols need knowledge of one-hop neighbors. In this paper we study the problem of neighbor discovery in a static and s ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Routing and search on large scale networks

Dominique Florian Tschopp

In this thesis, we address two seemingly unrelated problems, namely routing in large wireless ad hoc networks and comparison based search in image databases. However, the underlying problem is in essence similar and we can use the same strategy to attack t ...

EPFL2010

Collaborative routing in mobile partitioned networks

Natasa Sarafijanovic-Djukic

Embedded wireless networks find a broad spectrum of applications in transportation, environmental monitoring, logistics, supply chain management, and "pocketswitched" communication. The node mobility patterns in these applications tend to give rise to spat ...

EPFL2010

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Dominique de Werra, Bernard Ries

Given an undirected graph G = (V, E) with matching number nu(G), a d-blocker is a subset of edges B such that nu((V, E \ B))

2010

On the Tradeoff between Trust and Privacy in Wireless Ad Hoc Networks

Jean-Pierre Hubaux, Maxime Raya, Reza Shokri

As privacy moves to the center of attention in networked systems, and the need for trust remains a necessity, an important question arises: How do we reconcile the two seemingly contradicting requirements? In this paper, we show that the notion of data-cen ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

MARGIN: Maximal frequent subgraph mining

Ramachandra Satyanarayana Valluri

The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal su ...

2010