Tree width and Combinatorial Optimization (TACO)

Samenvatting

Boombreedte (-treewidth-) is een maat van grafen. Bekend is dat veel problemen die in het algemeen moeilijk (bijv. NP-volledig) zijn voor willekeurige grafen, (asymptotisch) snelle algoritmen hebben wanneer de boombreedte van de graaf uit de input klein (zeg, begrensd door een gegeven constante) is.
Het belang hiervan was tot dusverre slechts in de theoretische analyse van algoritmen. Dit project beoogt om de methode bruikbaar te maken om problemen uit actuele netwerktoepassingen daadwerkelijk te kunnen oplossen.

Een van de obstakels bij de toepassing van boombreedte in de praktijk is dat het vaak moeilijk is om een goede -boomdecompositie- (met kleine boombreedte) van een gegeven graaf te vinden.

Kenmerken

Projectnummer

631.000.001

Hoofdaanvrager

Dr. H.L. Bodlaender

Verbonden aan

Universiteit Utrecht, Faculteit Bètawetenschappen, Departement Informatica

Uitvoerders

E. Bachoore MSc, Drs. R.J.P. Bovendeerd, Dr. A. Grigoriev, Dr. E.J. van Leeuwen

Looptijd

01/02/2002 tot 25/09/2009