1Fully Dynamic Representations of Interval Graphs

Christophe Crespelle

Description

1Fully Dynamic Representations of Interval Graphs Christophe Crespelle LIP6 CNRS - University of Paris 6

• fully dynamic


• result updated


• result


• interval graphs


• minimal models


• vertex insertion


• updated representation

Sujets

• Result
• Minimal models

Informations

• Publié par: pefav
• Nombre de lectures: 6
• Langue: English

Extrait

Fully

1

Dynamic Representations of Interval Graphs

Christophe Crespelle

LIP6

CNRS - University of Paris 6

1 2 3 . . .

Plan

Problem and difficulty

Representations

Vertex insertion

of

Interval

Graphs

2

roglmhtiscRmiogectini Aon tyul

Interval graph?

Interval graphs

Updated representation?

di nd icff borPamelI   .

a

b x d c e

a

e c d

a b Cost? Updated result

b

Dynamic Algorithms

a b Result

naDy 3

Pr  . Indmaleob luciffid

e

d

c

a

b

yt rvalIntehsgrap

e

c

d

d e c

4

d b c

a b c

a

b