Kopafbeelding publicaties CPB

An efficient method for detecting redundant feedback vertices.

CPB Discussion Paper 29, 2 april 2004

De feedbackknoopverzameling van een gerichte graaf knipt alle gesloten paden in de gerichte graaf door.

Zo'n verzameling kan worden verkregen met behulp van het Levy-Low contractie algoritme, dat een kleine feedbackverzameling kan genereren die echter niet altijd minimaal van omvang is omdat het algoritme soms een heuristische keuze moet maken om de graaf geheel te kunnen reduceren. Dit kan ertoe leiden dat elementen van de feedbackverzameling overbodig zijn in de zin dat ze geen gesloten pad van de oorspronkelijke gerichte graaf doorknippen. In dit stuk wordt een tweetal algoritmes ontwikkeld om dergelijke overbodige feedbackknopen efficiƫnt op te sporen. De algoritmes worden toegepast op de analyse van grote niet-lineaire genormaliseerde stelsels vergelijkingen en op de feedbackverzamelingen van een reeks gerichte grafen die gebruikt zijn door anderen. Experimenten tonen aan dat de algoritmes een significante verbetering zijn ten opzichte van het standaard rechttoe, rechtaan algoritme.

Deel deze pagina