Publication

Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective

Publications associées (33)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Minimum clique partition in unit disk graphs

János Pach

The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting poi ...

Springer Verlag2011

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

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

k-Edge-Connectivity: Approximation and LP Relaxation

David Pritchard

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

On the computational complexity of periodic scheduling

Thomas Rothvoss

In periodic scheduling jobs arrive regularly and have to be executed on one or several machines or processors. An enormous amount of literature has been published on this topic, e.g. the founding work of Liu & Layland [LL73] is among the top cited computer ...

EPFL2009

On the Optimal Placement of Mix Zones

Jean-Pierre Hubaux, Julien Freudiger, Reza Shokri

In mobile wireless networks, third parties can track the location of mobile nodes by monitoring the pseudonyms used for identification. A frequently proposed solution to protect the location privacy of mobile nodes suggests to change pseudonyms in regions ...

Springer2009

Tracking the visual focus of attention for a varying number of wandering people

Daniel Gatica-Perez, Jean-Marc Odobez, Silèye Oumar Ba, Kevin Smith

In this article, we define and address the problem of finding the visual focus of attention for a varying number of wandering people (VFOA-W) -- determining where a person is looking when their movement is unconstrained. VFOA-W estimation is a new and impo ...

2008

Representative explanations for over-constrained problems

Boi Faltings, Pearl Pu Faltings

In many interactive decision making scenarios there is often no solution that satisfies all of the user's preferences. The decision process can be helped by providing explanations. Relaxations show sets of consistent preferences and, thus, indicate which p ...

American Association for Artificial Intelligence, Menlo Park, CA 94025-3496, United States2007

Network Correlated Data Gathering with Explicit Communication: NP-Completeness and Algorithms

Martin Vetterli, Razvan Cristescu

We consider the problem of correlated data gathering by a network with a sink node and a tree based communication structure, where the goal is to minimize the total trans- mission cost of transporting the information collected by the nodes, to the sink nod ...

2006

Evaluation of Input Parameterization for Batch Process Optimization

Dominique Bonvin, Alejandro Gabriel Marchetti, Carsten Welz

For the optimization of dynamic systems, it is customary to use measurements to combat the effect of uncertainty. In this context, an approach that consists of tracking the necessary conditions of optimality is gaining in popularity. The approach relies st ...

2006

New approaches for virtual private network design

Friedrich Eisenbrand

Virtual private network design is the following NP-hard problem. We are given a communication network, represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The ...

2005

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

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