Dynamic Algorithms via Forbidden-Set Labeling

Cyril Gavoille

hal-00656916, version 1

Dynamic Algorithms via Forbidden-Set Labeling

Cyril Gavoille (, ) ^1, 2, 3

First International Workshop on Dynamic Systems (DYNAM) (2011)

Abstract: Forbidden-set labeling schemes is a way to associate with each node of a graph G a compact data-structure, i.e., a short label, supporting queries Q(s,t,X) between any two nodes (s,t) of G\X where X is any set of "forbidden" nodes of G. The query Q(s,t,X) must be solved from the labels of the nodes involved in the query only, without any other source of information. Several important distributed applications are captured by this framework, like for instance fault-tolerant and policy routing in the Internet. In this talk, I show how to derive new time-efficient algorithms for some problems in dynamic graphs.

1: Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
2: CEPAGE (INRIA Bordeaux - Sud-Ouest)
INRIA – CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
3: Institut Universitaire de France (IUF)
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

hal-00656916, version 1
http://hal.archives-ouvertes.fr/hal-00656916
oai:hal.archives-ouvertes.fr:hal-00656916
From: Cyril Gavoille <>
Submitted on: Thursday, 5 January 2012 14:47:08
Updated on: Thursday, 5 January 2012 14:47:08

See detailed view

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Invited conferences</head>
<biblStruct type="article" xml:id="hal-00656916"><analytic>
<author><persName><forename>Cyril</forename><surname>Gavoille</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">CEPAGE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">IUF</orgName>
<orgName type="team">Institut Universitaire de France</orgName>
<country>FR</country>
<orgName type="institution">Ministère de l'Enseignement Supérieur et de la Recherche Scientifique</orgName>
</affiliation>
</author>
<title type="main" level="a">Dynamic Algorithms via Forbidden-Set Labeling</title></analytic><monogr><meeting>First International Workshop on Dynamic Systems (DYNAM)</meeting><imprint><pubPlace><settlement>LASS, Toulouse</settlement><country>France</country></pubPlace><biblScope type="publicationDate">2011-12-12</biblScope></imprint></monogr><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00656916</idno></biblStruct>
</listBibl>
</listBibl>