Publication

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Publications associées (38)

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

On the use of graphs in discrete tomography

Dominique de Werra, Bernard Ries

In this tutorial paper, we consider the basic image reconstruction problem which stems from discrete tomography. We derive a graph theoretical model and we explore some variations and extensions of this model. This allows us to establish connections with s ...

2010

Many maneuvers of Unmanned Aerial Vehicles (UAV) can be considered within a framework of trajectory following. Though this issue can differ from one application to another, they all share the same problem of finding an optimal path (or signal) to perform t ...

2009

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Zoltán Miklós

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, i ...

2009

Distributed Scalable Multi-Robot Learning using Particle Swarm Optimization

Alcherio Martinoli, James Pugh

Designing effective behavioral controllers for mobile robots can be difficult and tedious; this process can be circumvented by using online learning techniques which allow robots to generate their own controllers online in an automated fash- ion. In multi- ...

2009

Velocity-Scheduling Control for a Unicycle Mobile Robot: Theory and Experiments

Dominique Bonvin, Philippe Müllhaupt, Davide Buccieri, Damien Perritaz

Improvement over classical dynamic feedback linearization for a unicycle mobile robots is proposed. Compared to classical extension, the technique uses a higher-dimensional state extension, which allows rejecting a constant disturbance on the robot rotatio ...

2009

New Results on Optimizing Rooted Triplets Consistency

A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets ...

Springer2008

Approach to time dependence and reliability in dynamic route guidance

Yixing Chen

This paper presents a methodology for increasing the reliability of route suggestions in route guidance systems. The procedure, based on the A* path-finding algorithm and Chen's link penalty method, involves penalizing links with a high risk of being conge ...

National Academy of Sciences2007

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

Precoloring with cliques and stable sets in cographs

Tinaz Ekim

Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optim ...

2006

An Integrated Approach to Real-Time Mobile Robot Control in Partially Known Indoor Environments

In this paper we present a navigation method for mobile robots in partially known indoor environments based on integration of graph based search algorithms and dynamic window local obstacle avoidance method. With the attention on a dynamic environment thre ...

2005