A. Juancarlo, T. D. Nez, L. Barra, and B. Pérez, Dual graph representation of transport networks, Transportation Research Part B: Methodological, vol.30, issue.3, 1996.

S. Abiteboul, T. Chan, E. Kharlamov, W. Nuu, and P. Senellart, Capturing continuous data and answering aggregate queries in probabilistic XML, ACM Transactions on Database Systems, vol.36, issue.4, p.45, 2011.
DOI : 10.1145/2043652.2043658

URL : https://hal.archives-ouvertes.fr/hal-00677722

I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck, Highway Dimension, Shortest Paths, and Provably EEcient Algorithms, SODA, 2010.
DOI : 10.1137/1.9781611973075.64

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.193.5501

E. Adar and C. Re, Managing Uncertainty in Social Networks, IEEE Data Eng. Bull, vol.30, issue.2, 2007.

T. Akiba, C. Sommer, and K. Kawarabayashi, Shortest-path queries for complex networks, Proceedings of the 15th International Conference on Extending Database Technology, EDBT '12, 2012.
DOI : 10.1145/2247596.2247614

A. Amarilli, P. Bourhis, and P. Senellart, Provenance Circuits for Trees and Treelike Instances, ICALP, 2015.
DOI : 10.1007/978-3-662-47666-6_5

URL : https://hal.archives-ouvertes.fr/hal-01178399

A. Amarilli, P. Bourhis, and P. Senellart, Tractable Lineages on Treelike Instances, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '16, 2016.
DOI : 10.1145/2902251.2902301

URL : https://hal.archives-ouvertes.fr/hal-01336514

. Stefan, D. G. Arnborg, A. Corneil, and . Proskuworski, Complexity of nding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, vol.8, issue.2, 1987.

S. Arnborg and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, vol.23, issue.1, 1989.
DOI : 10.1016/0166-218X(89)90031-0

URL : http://doi.org/10.1016/0166-218x(89)90031-0

S. Asthana, O. D. King, F. D. Gibbons, and F. P. Roth, Predicting Protein Complex Membership Using Probabilistic Network Reliability, Genome Research, vol.14, issue.6, 2004.
DOI : 10.1101/gr.2203804

URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC419795

O. Michael and . Ball, Computational Complexity of Network Reliability Analysis: An Overview, IEEE Trans. Reliability, vol.35, issue.3, 1986.

P. Barceló, L. Libkin, and J. L. Reuuer, 2014. erying Regular Graph Paaerns, J. ACM Article, vol.61, issue.8, p.54, 2014.

L. Hans and . Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM J. Comput, vol.25, p.6, 1996.

F. Chiericheei, R. Kumar, S. Laaanzi, M. Mitzenmacher, A. Panconesi et al., On compressing social networks, KDD, 2009.

E. Cohen, E. Halperin, H. Kaplan, and U. Zwick, Reachability and Distance eries via 2-Hop Labels, SIAM J. Comput, vol.32, p.5, 2003.
DOI : 10.1137/s0097539702403098

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.1278

N. Nilesh, D. Dalvi, and . Suciu, EEcient query evaluation on probabilistic databases, VLDB J, vol.16, issue.4, 2007.

G. Di-baaista and R. Tamassia, On-line graph algorithms with SPQR-trees, ICALP, 1990.
DOI : 10.1007/BFb0032061

W. Edsger and . Dijkstra, A note on two problems in connexion with graphs, Numer. Math, vol.1, 1959.

P. Domingos and M. Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '01, 2001.
DOI : 10.1145/502512.502525

W. Fan, J. Li, X. Wang, and Y. Wu, 2012. ery preserving graph compression, SIGMOD Conference
URL : https://hal.archives-ouvertes.fr/hal-01313927

G. S. Fishman, A Comparison of Four Monte Carlo Methods for Estimating the Probability of s-t Connectedness, IEEE Transactions on Reliability, vol.35, issue.2, 1986.
DOI : 10.1109/TR.1986.4335388

J. Ghosh, H. Q. Ngo, S. Yoon, and C. Qiao, On a Routing Problem Within Probabilistic Graphs and its Application to Intermiiently Connected Networks, INFOCOM, 2007.
DOI : 10.1109/infcom.2007.201

C. Gutwenger and P. Mutzel, A Linear Time Implementation of SPQR-Trees, Graph Drawing, 2000.
DOI : 10.1007/3-540-44541-2_8

H. W. Hao-he, P. S. Yang, and . Yu, Compact reachability labeling for graph-structured data, Proceedings of the 14th ACM international conference on Information and knowledge management , CIKM '05, 2005.
DOI : 10.1145/1099554.1099708

E. John, R. E. Hopcroo, and . Tarjan, Dividing a Graph into Triconnected Components, SIAM J. Comput, vol.2, p.3, 1973.

E. John, R. E. Hopcroo, and . Tarjan, EEcient Algorithms for Graph Manipulation [H] (Algorithm 447), Commun. ACM, vol.16, p.6, 1973.

M. Hua and J. Pei, Probabilistic path queries in road networks: traac uncertainty aware path selection, EDBT, 2010.

R. Jin, L. Liu, B. Ding, and H. Wang, Distance-constraint reachability computation in uncertain graphs, Proceedings of the VLDB Endowment, vol.4, issue.9, p.9, 2011.
DOI : 10.14778/2002938.2002941

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.295.5041

B. Kanagal and A. Deshpande, Lineage processing over correlated probabilistic databases, Proceedings of the 2010 international conference on Management of data, SIGMOD '10, 2010.
DOI : 10.1145/1807167.1807241

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.207.2917

A. Khan and F. Bonchi, Aristides Gionis, and Francesco Gullo. 2014. Fast Reliability Search in Uncertain Graphs, EDBT

M. Kuramochi and G. Karypis, Frequent subgraph discovery, Proceedings 2001 IEEE International Conference on Data Mining, 2001.
DOI : 10.1109/ICDM.2001.989534

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.7488

D. Liben-nowell and J. M. Kleinberg, e link-prediction problem for social networks, JASIST, vol.58, issue.7, 2007.
DOI : 10.1002/asi.20591

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.163.6528

S. Maniu, B. Cautis, and T. Abdessalem, Building a signed network from interactions in Wikipedia, Databases and Social Networks on, DBSocial '11, pp.19-24, 2011.
DOI : 10.1145/1996413.1996417

URL : https://hal.archives-ouvertes.fr/hal-00703506

S. Maniu, R. Cheng, and P. Senellart, ProbTree: A ery-EEcient Representation of Probabilistic Graphs, Proc. BUDA. Workshop without formal proceedings, 2014.

E. J. Mark, S. H. Newman, D. J. Strogatz, and . Waas, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E, vol.64, issue.2, pp.26118-26135, 2001.

C. H. Papadimitriou, Computational Complexity, 1994.

O. Papapetrou, E. Ioannou, and D. Skoutas, EEcient discovery of frequent subgraph paaerns in uncertain graph databases, EDBT, 2011.

M. Potamias and F. Bonchi, Aristides Gionis, and George Kollios. 2010. k-Nearest Neighbors in Uncertain Graphs, 2010.

N. Robertson and P. D. Seymour, Graph minors. III. Planar tree-width, Journal of Combinatorial Theory, Series B, vol.36, issue.1, 1984.
DOI : 10.1016/0095-8956(84)90013-3

URL : http://doi.org/10.1006/jctb.1999.1919

A. Mohammad and . Safari, D-Width: A More Natural Measure for Directed Tree Width, MFCS, 2005.

P. Sen and A. Deshpande, Representing and erying Correlated Tuples in Probabilistic Databases, ICDE, 2007.
DOI : 10.1109/icde.2007.367905

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.473.4456

S. Seufert, A. Anand, S. Bedathur, and G. Weikum, FERRARI: Flexible and efficient reachability range assignment for graph indexing, 2013 IEEE 29th International Conference on Data Engineering (ICDE), 2013.
DOI : 10.1109/ICDE.2013.6544893

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.365.2894

A. Souihli and P. Senellart, Optimizing approximations of DNF query lineage in probabilistic XML, 2013 IEEE 29th International Conference on Data Engineering (ICDE), 2013.
DOI : 10.1109/ICDE.2013.6544869

URL : https://hal.archives-ouvertes.fr/hal-00874442

T. William and . Tuue, Connectivity in graphs, Mathematical Expositions, vol.15, 1966.

G. Leslie and . Valiant, e Complexity of Enumeration and Reliability Problems, SIAM J. Comput, vol.8, p.3, 1979.

F. Wei, TEDI, Proceedings of the 2010 international conference on Management of data, SIGMOD '10, 2010.
DOI : 10.1145/1807167.1807181

Z. Zou, H. Gao, and J. Li, Discovering frequent subgraphs over uncertain graph databases under probabilistic semantics, Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '10, 2010.
DOI : 10.1145/1835804.1835885