Efficient synthesis of consistent graphs

A consistent graph is a graph with zero cyclic sum of weights of edges along all loops. Given a number of possible weights for each edge, we study the problem of synthesizing consistent graphs, i.e. to find the appropriate combinations of weights, which form consistent graphs. This problem plays an important role in, e.g. source localization based on time difference of arrival (TDOA). By using the concept of loop matrix known from the electric network theory, we propose some novel systematic approaches for the efficient synthesis of consistent graphs. We describe our algorithms, demonstrate their performance and compare their computational complexity, both in theory and in experiments.