Separating codes and traffic monitoring
BELLITTO, Thomas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
BELLITTO, Thomas
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Réduire
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Langue
en
Article de revue
Ce document a été publié dans
Theoretical Computer Science. 2017
Elsevier
Résumé en anglais
This paper studies the problem of traffic monitoring which consists of differentiating a set of walks on a directed graph by placing sensors on as few arcs as possible. The problem of characterising a set of individuals ...Lire la suite >
This paper studies the problem of traffic monitoring which consists of differentiating a set of walks on a directed graph by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known, but traffic monitoring presents new challenges that the previous models of separation fall short from modelling such as taking into account the multiplicity and order of the arcs in a walk. We introduce a new and stronger model of separation based on languages that generalises the traffic monitoring problem. We study three subproblems with practical applications and develop methods to solve them by combining integer linear programming, separating codes and language theory.< Réduire
Origine
Importé de halUnités de recherche