Approximative Graphenprodukte

Graphenprodukte treten in verschiedensten Zusammenhängen und Kontexten auf, von der Informatik über die Theoretische Biologie bis zum Computational Engineering. Abstrakt betrachtet treten dieselben mathematischen und algorithmischen Fragen auf. Für jedes der drei kommutativen Standardprodukte von Graphen, also das Kartesische, das starke und das direkte Produkt, ist es möglich eine Reihe von Fragen zunehmender Komplexität zu stellen: Wie sehr kann man ein Produkt stören oder verändern, sodass die Produktstruktur auch weiterhin erkennbar und eindeutig ist? Wie kann man feststellen, ob ein gegebener Graph einen faktorisierbaren Teilgraphen hat, sei er nun induziert, isometrisch oder konvex? Was geschieht, wenn man nur approximative Faktorisierbarkeit verlangt? Im Hinblick auf das praktische Interesse an approximativer Faktorisierbarkeit von Graphen in den Bereichen Computational Biology und Computational Engineering ist es erstaunlich, dass dieser Problemkreis bisher wenig oder gar nicht systematisch untersucht wurde. In diesem Forschungsvorhaben soll sowohl die mathematische Struktur von approximativen Graphenprodukten untersucht werden als auch deren algorithmische Aspekte. Obwohl die Mehrzahl der obgenannten Probleme NP-vollständig sein wird, ist es dennoch von Bedeutung exakte Algorithmen, exakte Approximationen, und heuristische Vorgansweisen zu untersuchen und zu vergleichen.

Graphenprodukte treten in verschiedensten Zusammenhängen und Kontexten auf, von der Informatik über die Theoretische Biologie bis zum Computational Engineering. Abstrakt betrachtet treten dieselben mathematischen und algorithmischen Fragen auf. Für jedes der drei kommutativen Standardprodukte von Graphen, also das Kartesische, das starke und das direkte Produkt, ist es möglich eine Reihe von Fragen zunehmender Komplexität zu stellen: Wie sehr kann man ein Produkt stören oder verändern, sodass die Produktstruktur auch weiterhin erkennbar und eindeutig ist? Wie kann man feststellen, ob ein gegebener Graph einen faktorisierbaren Teilgraphen hat, sei er nun induziert, isometrisch oder konvex? Was geschieht, wenn man nur approximative Faktorisierbarkeit verlangt? Im Hinblick auf das praktische Interesse an approximativer Faktorisierbarkeit von Graphen in den Bereichen Computational Biology und Computational Engineering ist es erstaunlich, dass dieser Problemkreis bisher wenig oder gar nicht systematisch untersucht wurde. In diesem Forschungsvorhaben soll sowohl die mathematische Struktur von approximativen Graphenprodukten untersucht werden als auch deren algorithmische Aspekte. Obwohl die Mehrzahl der obgenannten Probleme NP-vollständig sein wird, ist es dennoch von Bedeutung exakte Algorithmen, exakte Approximationen, und heuristische Vorgansweisen zu untersuchen und zu vergleichen.