Definitions and preliminaries An incremental algorithm
54 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Definitions and preliminaries An incremental algorithm

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
54 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Definitions and preliminaries An incremental algorithm Complexity analysis An efficient split decomposition algorithm Christophe Paul CNRS - LIRMM - Universite Montpellier II, France May 22, 2008 Joint work with D. Corneil (U. of Toronto), E. Gioan (CNRS LIRMM) and M. Tedder (U. of Toronto) C. Paul An efficient split decomposition algorithm

  • complexity analysis

  • merging cost

  • algorithm

  • split decomposition

  • lirmm - universite montpellier

  • lexbfs amortized


Sujets

Informations

Publié par
Nombre de lectures 20
Langue English
Poids de l'ouvrage 7 Mo

Extrait

mhtiroglanoitisopmocedtilpstneicffienAluaP.CsisylanaytixelpMay22,2008

mChristophePaul

oCNRS-LIRMM-Universite´MontpellierII,France

Calgorithm

mAnefficientsplitdecomposition

hJointworkwith
D.Corneil
(U.ofToronto),
E.Gioan
(CNRSLIRMM)
and
M.Tedder
(U.ofToronto)

tiroglalatnemercninAseiranimilerpdnasnoitinfieD
mhtiroglanoitisopmocedtilpstneicffienAluaP.C.mhtiroglanoitisopmocedraludom)m+n(O)?relpmisneve(eromeno:tceffeediS3]49’darnipS[)2n(O:suoiverPshpargelcricfomhtiroglanoitingocer))m,n(α)m+n((OnA2sisylanaytixelpmoCmhtiroglalatnemercninAseiranimilerpdnasnoitinfieDPrevious:
O
(
n
2
)[Ma,Spinrad’94],
O
(
n
+
m
)[Dahlhaus’94]

1

splitdecompositionofanarbitrary(undirected)graph.

A(simple?)
O
((
n
+
m
)
α
(
n
,
m
))algorithmtocomputethe

Results

sisylanaytixelpmoCmhtiroglalatnemercninAseiranimilerpdnasnoitinfieDmhtiroglanoitisopmocedtilpstneicffienAluaP.C.mhtiroglanoitisopmocedraludom)m+n(O)?relpmisneve(eromeno:tceffeediS3Previous:
O
(
n
2
)[Spinrad’94]

2
An
O
((
n
+
m
)
α
(
n
,
m
))recognitionalgorithmofcirclegraphs

Previous:
O
(
n
2
)[Ma,Spinrad’94],
O
(
n
+
m
)[Dahlhaus’94]

1
A(simple?)
O
((
n
+
m
)
α
(
n
,
m
))algorithmtocomputethe
splitdecompositionofanarbitrary(undirected)graph.

Results

mhtiroglanoitisopmocedtilpstneicffienAluaP.CsisylanaytixelpmoCmhtiroglalatnemercninAseiranimilerpdnasnoitinfieD3
Sideeffect:onemore(evensimpler?)
O
(
n
+
m
)modular
decompositionalgorithm.

Previous:
O
(
n
2
)[Spinrad’94]

2
An
O
((
n
+
m
)
α
(
n
,
m
))recognitionalgorithmofcirclegraphs

Previous:
O
(
n
2
)[Ma,Spinrad’94],
O
(
n
+
m
)[Dahlhaus’94]

1
A(simple?)
O
((
n
+
m
)
α
(
n
,
m
))algorithmtocomputethe
splitdecompositionofanarbitrary(undirected)graph.

Results

nimilerpdnasnoitinfieDmhtiroglanoitisopmocedtilpstneicffienAluaP.CConclusion

Amortizedmergingcost

LexBFS

Complexityanalysis

3

Anincrementalalgorithm

2

1

Definitionsandpreliminaries

sisylanaytixelpmoCmhtiroglalatnemercninAseira
mhtiroglanoitisopmocedtilpstneicffienAluaP.CGhpargaybdellebalsiTfokeergedfosisylanaytixelpmoCmhtiroglalatnemercninAseiranimilerpdnasnoitinfieDv

thereisabijection
ρ
v
fromthetree-edgesincidentto
v
tothe
verticesof
G

eachnode
v
on
k
vertices

F∈v

A
graph-labelledtree
isapair(
T
,
F
)with
T
atreeand
F
asetof
graphssuchthat:

Graphlabeledtree

mhtiroglanoitisopmocedtilpstneicffienAluaP.C,T(sisylanaytixelpmoCmhtiroglalatnemercninAseiranimilerpdnasnoitinfieDxy

E
(
G
S
(
T
,
F
))iff
ρ
v
(
uv
)
ρ
v
(
vw
)

E
(
G
v
),

tree-edges
uv
,
vw
onthe
x
,
y
-pathin
T

Givenagraphlabelledtree
leavesof
T
asverticesand

F
),thegraph
G
S
(
T
,
F
)hasthe

pdnasnoitinfieDmhtiroglanoitisopmocedtilpstneicffienAluaP.C,)xy

E
(
G
S
(
T
,
F
))iff
ρ
v
(
uv
)
ρ
v
(
vw
)

E
(
G
v

tree-edges
uv
,
vw
onthe
x
,
y
-pathin
T

Givenagraphlabelledtree
leavesof
T
asverticesand

F
),thegraph
G
S
(
T
,
F
)hasthe

,T(sisylanaytixelpmoCmhtiroglalatnemercninAseiranimiler
mhtiroglanoitisopmocedtilpstneicffienAluaP.Ce−TfoseertbusowtehteraBTdnaATerehwBTfotesfaelehtBdnaATfotesfaelehtsiA:Gfo)B,A(tilpsasenfiedTfoeegdeeertynanehT.Gfoeertdellebalhpargaeb)F,T(teLtilpS;2>sisylanaytixelpmoCmhtiroglalatnemercninAseiranimilerpdnasnoitinfieDfor
x

A
and
y

B
,
xy

E
iff
x

N
(
B
)and
y

N
(
A
).

|
A
|
>
2,
|
B
|

split
iff

Abipartition(
A
,
B
)oftheverticesofagraph
G
=(
V
,
E
)isa

tilpS

foeegdeeertynanehT.GfoeertsisylanaytixelpmoCmhtiroglalatnemercninAseiranimilerpdnasnoitinfieDLet(
T
,
F
)beagraphlabelled
T
definesasplit(
A
,
B
)of
G
:
A
istheleafsetof
T
A
and
B
theleafsetof
T
B
where
T
A
and
T
B
arethetwosubtreesof
T

e

tilpS

mhtiroglanoitisopmocedtilpstneicffienAluaP.C

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents