Effiziente Algorithmen für Graphen mit beschränkter Cliquenweite

• Antragsteller: Professor Dr. Egon Wanke
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 1999 bis 2003
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5231986

In diesem Forschungsprojekt werden algorithmische Eigenschaften von Graphen mit beschränkter NLC-Weite untersucht. Solche knotenmarkierte Graphen werden mit Operationen aufgebaut, die nach bzw. während einer disjunkten Vereinigung von zwei Graphen Kanten zwischen Knoten mit vorgegebenen Markierungen einfügen. Ein anschließendes Ummarkieren der Knoten ist ebenfalls erlaubt. Gleich markierte Knoten werden jedoch immer gleich behandelt. Die Anzahl k der zur Verfügung stehenden Knotenmarkierungen ist das Maß für die Cliquenweite bzw. NLC-Weite. Graphen mit beschränkter Cliquenweite bzw. NLC-Weite besitzen eine natürliche Baumstruktur, welche wie bei allen anderen baumstrukturierten Graphen zur effizienten Lösung von Graphenproblemen genutzt werden kann.Dieses Forschungsvorhaben verfolgt die folgenden vier Richtungen. 1) Es sollen effiziente Algorithmen entwickelt werden, die zu einem gegebenen Graphen die unterliegende Baumstruktur bestimmen. 2) Es sollen allgemeine Vorgehensweisen entwickelt werden, mit denen NP-schwere Grapheigenschaften und Optimierungsprobleme auf Graphen mit beschränkter Cliquenweite bzw. beschränkter NLC-Weite in polynomieller Zeit gelöst werden können. 3) Die Klasse der Graphen mit beschränkter Cliquenweite bzw. beschränkter NLC-Weite soll in der Hierarchie der speziellen Graphklassen eingeordnet werden. 4) Die praktische Anwendbarkeit der Theorie soll experimentell ausgewertet werden.

• DFG-Verfahren: Sachbeihilfen