Effiziente Synthese konsistenter Graphen und ihre Anwendungen in der digitalen Signalverarbeitung

• Antragsteller: Professor Dr.-Ing. Bin Yang
• Fachliche Zuordnung: Elektronische Halbleiter, Bauelemente und Schaltungen, Integrierte Systeme, Sensorik, Theoretische Elektrotechnik
• Förderung: Förderung von 2009 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 66414569

Ein konsistenter Graph ist ein gewichteter Graph, in dem die zyklische Summe der Kantenwerte entlang jeder Masche null ist. Solche Graphen spielen eine wichtige Rolle in elektrischen Netzwerken und auf Laufzeitdifferenz basierender Lokalisierung. Uns interessiert in diesem Vorhaben neben den Eigenschaften solcher Graphen vor allem deren effiziente Synthese aus gemessenen fehlerhaften Kantenwerten. Nachdem wir in der ersten Förderperiode die graphentheoretischen Grundlagen gelegt, die Eigenschaften konsistenter Graphen systematisch untersucht und einige effiziente Top-Down-Syntheseverfahren entwickelt haben, wollen wir in der zweiten Förderperiode neben der Verbesse¬¬¬rung der Top-Down-Verfahren auch Bottom-Up-Strategien verfolgen, die Stärken der beiden Ansätze zu einem noch effizienteren Hybrid-Ansatz kombinieren, die Synthesealgorithmen auf beliebige, auch nicht zusammenhängende, nur annähernd konsistente Graphen erweitern und schließlich deren Leistungsfähigkeit und Grenze in einer realen Anwendung aufzeigen.

• DFG-Verfahren: Sachbeihilfen