Tree width and Combinatorial Optimization (TACO)

Summary

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.

Details

Project number

631.000.001

Main applicant

Dr. H.L. Bodlaender

Affiliated with

Universiteit Utrecht, Faculteit B├Ętawetenschappen, Departement Informatica

Team members

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

Duration

01/02/2002 to 25/09/2009