Innerhalb unseres eigenen Institute haben sich noch zwei weitere Kooperationen ergeben, innerhalb derer wir Algorithmen für die effiziente Erkennung von Subgraphen entwickeln konnten. In einem ersten Projekt mit der Arbeitsgruppe um Kay Nieselt geht es um die Bestimmung von Cliquen in Netzwerken, die aus DNA-Sequenzvergleichen stammen. Wir konnten nachweisen, dass diese spezielle Art von Netzwerk eine Form des Intervallgraphen aus Intervallen unterschiedlicher Länge darstellt, und damit die Menge aller Cliquen in polynomieller Zeit berechenbar ist.
In einer zweiten Kooperation (mit der Arbeitsgruppe um Oliver Kohlbacher) geht es darum, Netzwerke aus chemischen Substanzen, die durch unterschiedliche Ähnlichkeitsmaße in ihrer Verwandtschaft zueinander charakterisiert werden, in geeigneter Weise und effizient zu clustern. Erste Versuche waren hier sehr ermutigend. Eine ähnliche Clusteranalyse haben wir auch für Netzwerke durchgeführt, die aus öffentlich zugänglichen Daten von Amazon.de erzeugt wurden.