Effiziente Synthese konsistenter Graphen und ihre Anwendungen in der digitalen Signalverarbeitung

点击翻译按钮获取中文摘要

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.