Network construction with subgraph connectivity constraints

Alon N, Asodi V (2005) Learning a hidden subgraph. SIAM J Discret Math 18(4):697–712

Alon N, Awerbuch B, Azar Y, Buchbinder N, Naor J (2003) The online set cover problem. In: Proceedings of the 35th annual ACM symposium on theory of, computing, pp. 100–105

Alon N, Awerbuch B, Azar Y, Buchbinder N, Naor J (2006) A general approach to online network optimization problems. ACM Trans Algorithms 2(4):640–660

Alon N, Beigel R, Kasif S, Rudich S, Sudakov B (2004) Learning a hidden matching. SIAM J Comput 33(2):487–501

Angluin D, Aspne, J, Reyzin L (2008) Optimally learning social networks with activations and suppressions. In: 19th International conference on algorithmic learning theory, pp. 272–286

Angluin D, Aspnes J, Reyzin L (2010) Inferring social networks from outbreaks. In: 21st International conference on algorithmic learning theory, pp. 104–118

Angluin D, Chen J (2008) Learning a hidden graph using $$O(\log n)$$ queries per edge. J Comput Syst Sci 74(4):546–556

Beigel R, Alon N, Kasif S, Apaydin MS, Fortnow L (2001) An optimal procedure for gap closing in whole genome shotgun sequencing. In: RECOMB, pp. 22–30

Booth KS, Lueker GS (1976) Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J Comput Syst Sci 13(3):335–379

Buchbinder N (2008) Designing competitive online algorithms via a primal-dual approach. Ph.D. thesis, Technion–Israel Institute of Technology, Haifa, Israel

Chockler G, Melamed R, Tock Y, Vitenberg R (2007) Constructing scalable overlays for pub-sub with many topics. In: PODC, pp. 109–118

Erdös P, Rényi A (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5:17–61

Feige U (1998) A threshold of ln for approximating set cover. J ACM 45(4):634–652

Gomez-Rodriguez M, Leskovec J, Krause A (2012) Inferring networks of diffusion and influence. TKDD 5(4):21

Grebinski V, Kucherov G (1998) Reconstructing a hamiltonian cycle by querying the graph: application to DNA physical mapping. Discret Appl Math 88(1–3):147–165

Gupta A, Krishnaswamy R, Ravi R (2009) Online and stochastic survivable network design. In: 41st Symposium on the theory of, computing, pp. 685–694

Korach E, Stern M (2003) The clustering matroid and the optimal clustering tree. Math Program 98 (1–3):345–414

Korach E, Stern M (2008) The complete optimal stars-clustering-tree problem. Discret Appl Math 156(4):444–450

Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability pcp characterization of np. In: STOC, pp. 475–484

Reyzin L, Srivastava N (2007) Learning and verifying graphs using queries with a focus on edge counting. In: 18th International conference on algorithmic learning theory, pp. 285–297

Saito K, Nakano R, Kimura M (2008) Prediction of information diffusion probabilities for independent cascade model. In: KES (3), pp. 67–75

Wolsey LA (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385–393