in einer Kombination aus graphentheoretischen Parametern und dem Packungsproblem.

Betrachten wir dazu eine Clique W des Kopplungsgraphen G = (V,E). Die Gesamtheit aller innerhalb dieser Clique angeforderten Dienste bezeichnen wir mit R_W, d. h., es ist R_W = _wWR_w. Da die Knoten einer Clique alle paarweise benachbart sind, muss jeder Block, der einem Knoten aus W zugewiesen wird, einen eigenen Kanal erhalten. Da die Gesamtheit dieser Blöcke aber einer Zerlegung von R_W entspricht, und p_M(R_W) die minimale Größe einer solchen Zerlegung ist, werden unabhängig von der konkreten Blockzuweisung stets mindestens p_M(R_W) Kanäle zur Versorgung aller Knoten in W benötigt. Der Wert p_M(R_W) stellt also eine untere Schranke für die Kanalzahl dar, die für das gesamte Netz benötigt wird. Die beste solche untere Schranke ist maxp_M(R_W), wobei das Maximum über alle Cliquen W von G genommen wird. Wir bezeichnen diese Größe auch als die Clique-Packungszahl. Die Clique-Packungszahl liefert uns also eine untere Schranke für das DAB-Blockzuweisungsproblem. Der besondere Vorteil dieser Kenngröße eines DAB-Netzes liegt darin, dass man sie aus den Eingabedaten errechnen kann, ohne irgendwelche konkreten Blockzuweisungen berücksichtigen zu müssen.

Da das Packungsproblem NP-vollständig ist, lässt sich auch die Clique-Packungszahl nur näherungsweise mittels einer verallgemeinerten Variante des in Abschnitt 4.1 erwähnten Carraghan-Pardalos-Algorithmus‘ errechnen. In der Praxis verwendet man dazu normalerweise die „Summen-Schranke“ _ss/M, die eine untere Schranke für die Packungszahl einer Menge liefert. (Z. B. hat die Dreier-Clique der Gebiete I, II und V in Abb. 3 Anforderungen, deren Gesamtbandbreite 24 drei Blöcke erfordert; daher ist die Blockzuweisung in Abb. 4(b) optimal.)

4.5.  Experimentelle Ergebnisse

Der oben vorgestellte Lösungsansatz für das DAB-Blockzuweisungsproblem wurde inzwischen im Rahmen einer Testumgebung realisiert und ersten Tests unterzogen. Wir führten dazu verschiedene Testserien mit zufällig erzeugten Kopplungsgraphen und Anforderungen durch. Als Kopplungsgraphen wurden dabei die bereits erwähnten Einheitskreisscheiben-Graphen verwendet, die sehr oft als einfaches Modell für Rundfunknetze verwendet werden und auf Grund ihrer geometrischen Struktur dem Aufbau realer Sendernetze recht nahe kommen.

Die (recht typischen) Ergebnisse einer solchen Testreihe sind in Abb. 5 zusammengefasst. Für diese Testreihe wurden n Kreisscheiben mit Durchmesser 0,25 im Einheitsquadrat [0,1] × [0,1] und r Dienste mit zufälligen ganzzahligen Bandbreiten im Intervall [1,5] verwendet. Die Blockgröße wurde auf M = 10 festgelegt. Jedem Knoten wurden zwischen 1 und 5 Dienste zufällig als Anforderung zugewiesen. Um den Einfluss der Parameter n und r auf die Ergebnisse der getesteten SFF- und GFF-Verfahren zu untersuchen, wurden jeweils 20 Tests mit jeder Kombination von n {20,50,100} und r {10,20,50,100} durchgeführt; dabei wurde jeweils eine bestimmte sequentielle Färbungsheuristik, der sogenannte „Smallest-Last“-Algorithmus, zur Berechnung der Kanalzuweisungen verwendet. Die dargestellten Ergebnisse beziehen sich auf die mit dem SFF- und dem GFF-Algorithmus erzielten Resultate sowie das beste dieser beiden (BEST). Dabei wurde jeweils die