Mathieu Chapelle1 Frederic Mazoit2 Ioan Todinca1

Mathieu Chapelle, Frédéric Mazoit, Ioan Todinca

Description

Constructing brambles Mathieu Chapelle1, Frederic Mazoit2, Ioan Todinca1 1LIFO – Universite d'Orleans 2LaBRI – Universite de Bordeaux I JGA'09 Montpellier 5–6 novembre 2009

• tree-like decompositions


• when restricted


• brambles revisited


• tree width


• width


• constructing brambles


• used when

Sujets

• Tree decomposition

Informations

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

Extrait

Mathieu

Constructing brambles

Chapelle 1 Fr,d´´eicerozaMti 2 , Ioan

1 LIFiverO–UndeO’is´tnaslre´ 2 UnI–BRLat´sierivedroBedeIxua

JGA’09 Montpellier 5–6 novembre 2009

Todinca 1

hTdeglaetirooCmhradblembevsritisceitevsnclusionandpersp

The algorithm

Conclusion and perspectives

Tree-decompositions and brambles revisited

The problem

1/2 -eerTmelborpehT 0 annsioitosmpcode

Tree-decompositions and brambles revisited

The problem

Conclusion and perspectives

The algorithm

compositmTree-deehrpboel 22/ T 0 orlgeaTheditisevrselbmarbdnasnoistivespecdpernonaulisoCcntimh

lemsprobhardlNP-pnloevidseloacbn rteain r l loiaomyn etcirtsernehwemi h,andglupapproactuoisnotsebus-lo baloolls taob ag in fostausu oitu oL .n tdgoarhpwstibhuonded∗-widths.

3/20

Tree-like decompositions

A popular technique used when dealing withN P-hard problems is todecomposethe input graph and then usedynamic programming.

heTborpTmel-eerocedulcnoCmhtiroglaetiecsperdpanonsibdarsnnatioipmsoedThisitsrevmbleevs euw-diht.,.. lAwl ,rank-width,cliq,htdnarbw-hchtdig.e.re:twie- sinapartesubdglu,hnargpatyehvilerscuresepoomec • d :rovaflemasniskro bottom-u ; • applya opisitnoihdscemovegiytnbid-wisth • ;ee ∗eht dnik rtfo

/302 orlbhTpeee-demTrposiecomdnasnoitselbmarbtesiviregoalhedTvitcseepdnepsrusclnaiothrionmC Asirkwoll erecmposvelyursi flevasnma edoc ro • : ueglb-suchoand,aootsiatbulosnoit ion; • app composit -mpuparpylbatoot dtwi∗-he • t e;reft edsihtybnevigsih glue,andraphthegni o dnikarastuspb shpahtiwnuob∗dedid-ws.th

A popular technique used when dealing withN P-hard problems is todecomposethe input graph and then usedynamic programming. e.g.:tree-width, branch-width, rank-width, clique-width, . . .

Tree-like decompositions

laro ilenraitemhwenrestrictedtogr lborpdraebnacsmeinedlvsominolypo bolaa n lgitnoosul sofu . LotNP-hsual

alsufusootL-hNPdparblroscemebnavlosnideylopnomialor lineartiemhwneertsirtcdehsapgrtounbothwidiw-∗ded

All works in same flavor: • decompose recursivelythe graph, and glue subparts in a kind of tree; • the∗-width is given by this decomposition; • apply abottom-upapproach, and glue sub-solutions to obtain a global solution.

A popular technique used when dealing withN P-hard problems is todecomposethe input graph and then usedynamic programming. e.g.:tree-width . ., branch-width, rank-width, clique-width, .

Tree-like decompositions

.sht sreptcvioiandnepmConclusalgorithetisehTdselbiverndsaambrsipoonticemoeed-merTorlbThep 3/20 se

3/2 -eerTmelborpehT 0 annsioitosmpcodesitirsvebmelbdarhmCooritealgedThevsceitsionncluerspandp

Tree-like decompositions

A popular technique used when dealing withN P-hard problems is todecomposethe input graph and then usedynamic programming. e.g.:tree-width, branch-width, rank-width, clique-width, . . .

All works in same flavor: • decompose recursivelythe graph, and glue subparts in a kind of tree; • the∗-width is given by this decomposition; • apply abottom-upapproach, and glue sub-solutions to obtain a global solution.

Lots of usualN P-hard problems can be solved in polynomial or linear time when restricted to graphs with bounded∗-widths.