Top-k Reliable Color Set in Uncertain Graphs
Andreas Nufer · Repository for Publications and Research Data (ETH Zurich) · 2015
In this thesis, we analyze the problem of finding the top-k edge colors that maximize the reliability between a set of source nodes and a set of destination nodes in an uncertain, edgecolored graph. Given more than one source and one destination, we further need to specify the maximization problem. Two types of maximization problems are studied. In the first, we maximize the pairwise reliability between nodes based on an aggregation function like Maximum, Average or Minimum. In the second, we maximize the connectivity between all nodes at once. The top-k color problem itself is NP-hard. We design effective, heuristic algorithms to solve these maximization problems in an efficient and reliable way. To carry this theoretical work on, we conduct an extensive empirical evaluation which shows that our solutions are scalable and highly accurate.