%%% INTRO: %%% FLUJOS EN REDES @book{FordFulkerson1962, author = {Ford, L. R. and Fulkerson, D. R.}, citeulike-article-id = {4083043}, keywords = {book}, posted-at = {2009-02-23 06:09:52}, priority = {0}, publisher = {Princeton University Press}, title = {Flows in Networks}, year = {1962} } @article {EvenTarjan1975, author = {Even, S. and Tarjan, R.E.}, title = {Network flow testing and graph connectivity}, journal = {SIAM J. Computing}, volume = {4}, pages = {507-518}, year = {1975} } %%% TEOREMA DE KIRCHHOFF COMPLEJIDAD COMPUTACIONAL (CAP 7 DE BIGGS Y ARTICULO ORIGINAL) @book{Biggs1993, title={Algebraic Graph Theory}, author={Biggs, N.}, isbn={9780521458979}, lccn={73086042}, series={Cambridge Mathematical Library}, year={1993}, publisher={Cambridge University Press} } @article {Kirchoff1847, author = {Kirchoff, G.}, title = {\"{U}ber die Aufl\"{o}sung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Str\"{o}me gef\"{u}hrt wird}, journal = {Ann. Phys. Chem.}, volume = {72}, pages = {497-508}, year = {1847} } %%% COMPLEJIDAD COMPUTACIONAL @book{Garey:1979:CIG:578533, author = {Garey, Michael R. and Johnson, David S.}, title = {Computers and Intractability: A Guide to the Theory of NP-Completeness}, year = {1979}, isbn = {0716710447}, publisher = {W. H. Freeman and Company}, address = {New York, NY, USA}, } @inproceedings{Cook1971, author = {Cook, Stephen A.}, title = {The complexity of theorem-proving procedures}, booktitle = {Proceedings of the third annual ACM symposium on Theory of computing}, series = {STOC '71}, year = {1971}, location = {Shaker Heights, Ohio, USA}, pages = {151--158}, numpages = {8}, doi = {10.1145/800157.805047}, acmid = {805047}, publisher = {ACM}, address = {New York, NY, USA}, } @incollection{Karp1972, author = {Karp, R. M.}, booktitle = {Complexity of Computer Computations}, citeulike-article-id = {3082225}, editor = {Miller, R. E. and Thatcher, J. W.}, keywords = {complexity, file-import-08-08-04}, pages = {85--103}, posted-at = {2008-08-04 21:01:04}, priority = {1}, publisher = {Plenum Press}, title = {Reducibility Among Combinatorial Problems}, year = {1972} } %%% COMPLEJIDAD DE LA CONFIABILIDAD CLASICA @article{Rosenthal1977, author = {Rosenthal, A.}, title = {Computing the Reliability of Complex Networks}, journal = {SIAM Journal on Applied Mathematics}, volume = {32}, number = {2}, pages = {384-393}, year = {1977} } @article{Valiant1979, author = {Valiant, L.}, journal = {SIAM Journal on Computing}, keywords = {comp, comprehensive, phd, ppi\_network}, number = {3}, pages = {410--421}, title = {The Complexity of Enumeration and Reliability Problems}, volume = {8}, year = {1979} } @article{provan83, author = {Provan, Scott J. and Ball, Michael O.}, journal = {SIAM Journal on Computing}, keywords = {comprehensive, phd, ppi\_network}, number = {4}, pages = {777--788}, posted-at = {2008-06-25 20:46:09}, priority = {2}, publisher = {SIAM}, title = {{The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected}}, volume = {12}, year = {1983} } %%%% CALCULO EXACTO @article {SatyaChang1983, author = {Satyanarayana, A. and Chang, Mark K.}, title = {Network reliability and the factoring theorem}, journal = {Networks}, volume = {13}, number = {1}, publisher = {Wiley Subscription Services, Inc., A Wiley Company}, issn = {1097-0037}, pages = {107--120}, year = {1983}, } @ARTICLE{6372698, author={Moskowitz, Fred}, journal={American Institute of Electrical Engineers, Part I: Communication and Electronics, Transactions of the}, title={The analysis of redundancy networks}, year={1958}, volume={77}, number={5}, pages={627-632}, keywords={Current measurement;Equations;Instrument transformers;Radar;Redundancy;Voltage measurement}, doi={10.1109/TCE.1958.6372698}, ISSN={0097-2452},} %%% CONFIABILIDAD CLASICA Y SISTEMAS BINARIOS ESTOCASTICOS @ARTICLE{Ball1986, author={Ball, Michael O.}, journal={IEEE Transactions on Reliability}, title={Computational Complexity of Network Reliability Analysis: An Overview}, year={1986}, month={aug. }, volume={35}, number={3}, pages={230 -239}, abstract={This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures for stochastic networks. We show how these problems are related to the more familiar computational network problems of recognizing certain subnetworks, finding optimal subnetworks, and counting certain subnetworks. We use these relationships to show that the k-terminal, the 2-terminal, and the all-terminal network reliability analysis problems are at least as hard as the renowned set of computationally difficult problems, NP-Complete. Finally, we discuss the impact of these results on how one should approach problem solving in this area.}, keywords={}, doi={10.1109/TR.1986.4335422}, ISSN={0018-9529}} %%% COMPLEJIDAD DCR @article{IJMHeur, title = {On the complexity of the Diameter-Constrained K-Reliability Problem}, journal = {Submitted - International Journal of Metaheuristics. Available at http://www2.um.edu.uy/psartor/robromsar2013.pdf}, volume = {}, number = { }, pages = { }, year = { }, issn = { }, author = {Eduardo Canale and H\'ector Cancela and Franco Robledo and Pablo Romero and Pablo Sartor}, keywords = {Network reliability}, keywords = {Survivability}, keywords = {Computational complexity} } @article{Canale2014457, title = {The complexity of computing the 2-K-reliability in networks}, journal = {Information Processing Letters}, volume = {114}, number = {9}, pages = {457 - 461}, year = {2014}, issn = {0020-0190}, doi = {http://dx.doi.org/10.1016/j.ipl.2014.03.010}, author = {Eduardo Canale and Héctor Cancela and Franco Robledo and Pablo Sartor}, } @article{SartorITOR2013a, author = {Canale, Eduardo and Cancela, H\'ector and Robledo, Franco and Rubino, Gerardo and Sartor, Pablo}, title = {On computing the 2-diameter-constrained {K}-reliability of networks}, journal = {International Transactions in Operational Research}, volume = {20}, number = {1}, issn = {1475-3995}, pages = {49--58}, keywords = {Network reliability, survivability, fault tolerance, diameter constraints, combinatorial problems, computational complexity}, year = {2013}, } @InProceedings{PR01, author={Petingi, L. and Rodriguez, J.}, title = {Reliability of networks with delay constraints}, booktitle = {Congressus Numerantium}, volume = {152}, pages = {117-12}, year = {2001}, } @INPROCEEDINGS{CP2001, author = {H'ector Cancela and Louis Petingi}, TITLE = {Diameter constrained network reliability: exact evaluation by factorization and bounds}, booktitle = {ICIL'2001 (International Conference on Industrial Logistics)}, PAGES = {359-366}, YEAR = {2001}, } @article{CP2004, author = {H'ector Cancela and Louis Petingi}, title = {Reliability of communication networks with delay constraints: computational complexity and complete topologies}, journal = {International Journal of Mathematics and Mathematical Sciences}, year = {2004}, volume = {2004}, issue = {29}, pages = {1551-1562} } @article{romeroallterminal, author = {Pablo Romero}, journal = {Premat}, publisher = {Premat}, title = {{On the Complexity of the Diameter Constrained Reliability}}, volume = {1}, year = {2014} } @article{CanaleRomeroarxiv, author = {Eduardo A. Canale and Pablo Romero}, title = {Diameter Constrained Reliability: Computational Complexity in terms of the diameter and number of terminals}, journal = {CoRR}, volume = {abs/1404.3684}, year = {2014}, ee = {http://arxiv.org/abs/1404.3684}, bibsource = {DBLP, http://dblp.uni-trier.de} } %% PROPIEDADES DE GRAFOS EXTREMALES @book{Bollobas2001, added-at = {2007-03-12T11:29:08.000+0100}, author = {Bollob\'as, B.}, biburl = {http://www.bibsonomy.org/bibtex/2a08b7937f79ce0cf9854806274e42ee1/vittorio.loreto}, citeulike-article-id = {827976}, editor = {Fulton, W. and Katok, A. and Kirwan, F. and Sarnak, P. and Simon, B. and Totaro, B.}, interhash = {d6845690efa62f6cf293b4acc97a569c}, intrahash = {a08b7937f79ce0cf9854806274e42ee1}, keywords = {2001 RMP_CFL bollobas graphs random}, priority = {5}, publisher = {Cambridge University Press}, timestamp = {2007-03-12T11:29:08.000+0100}, title = {Random Graphs}, year = 2001 } @book{BollobasEGT, title={Extremal Graph Theory}, author={Bollob{\'a}s, B.}, isbn={9780486435961}, lccn={77076680}, series={Dover Books on Mathematics Series}, year={2004}, publisher={Dover Publications} } @article{ErdosRenyi1959, author = {Erdos, P. and R\'enyi, A.}, title = {On Random Graphs}, journal = {Publicationes Mathematicae}, volume = {6}, year = {1959}, pages = {290-297} } @article{Gilbert1959, author = {Gilbert, E. N.}, title = {Random Graphs}, journal = {Annals of Mathematical Statistics}, volume = {30}, year = {1959}, pages = {1141-1144} } @article{Bollobas1981, jstor_articletype = {research-article}, title = {The Diameter of Random Graphs}, author = {Bollob\'as, B.}, journal = {Transactions of the American Mathematical Society}, jstor_issuetitle = {}, volume = {267}, number = {1}, jstor_formatteddate = {Sep., 1981}, pages = {pp. 41-52}, url = {http://www.jstor.org/stable/1998567}, ISSN = {00029947}, language = {English}, year = {1981}, publisher = {American Mathematical Society} } %%% ALGORITMOS DE APROXIMACION %% BASADO EN PATHSETS Y CUTSETS @PhdThesis{sartor:thesis, author = {Pablo Sartor}, title = {{Propri\'{e}t\'{e}s et m\'{e}thodes de calcul de la fiabilit\'{e} diam\`{e}tre-born\'{e}e des r\'{e}seaux}}, school = {INRIA/IRISA, Universit\'{e} de Rennes I}, year = 2013, address = {Rennes, France}, month = {december}, } %% MONTE CARLO E INTERPOLACION @INPROCEEDINGS{rndm13, AUTHOR={Franco Robledo and Pablo Gabriel Romero and Pablo Sartor}, TITLE={A novel Interpolation technique to address the {Edge-Reliability} Problem}, BOOKTITLE={RNDM'13 - 5th International Workshop on Reliable Networks Design and Modeling (RNDM'13)}, ADDRESS={Almaty, Kazakhstan}, PAGES={77-82}, DAYS={10}, MONTH={sep}, YEAR={2013}, KEYWORDS={All-terminal reliability; Monte Carlo; Newton interpolation; Hilbert space.}, ABSTRACT={In this paper we deal with the Edge-Reliability Problem: given a connected simple graph G = (V,E) with perfect nodes and links failing independently with equal probability 1-p,find the probability R\_G(p) that the network remains connected. The edge reliability R\_G(p) is a polynomial in p with degree m = |E|, and the exact computation of R\_G(p) is in the class of NP-Hard problems. However, the related literature is vast, and offers bounds and estimation techniques, as well as exponential algorithms to exactly find that polynomial. We propose a novel interpolation-based technique that exploits the structure of the Hilbert space L^2[0,1], and combines the efficiency of Newton interpolation with the simplicity of Monte Carlo reliability estimation in selected abscissas in [0,1]. The aim is to guide the polynomial search respecting algebraic properties of the target polynomial coefficients. We illustrate the effectiveness of the algorithm in the lights of a naive graph with limited size, and discuss several hints for future work.} } @article{Canale2014134, title = {Monte Carlo methods in diameter-constrained reliability }, journal = {Optical Switching and Networking }, volume = {14, Part 2}, number = {0}, pages = {134 - 148}, year = {2014}, note = {Special Issue on \{RNDM\} 2013 }, issn = {1573-4277}, doi = {http://dx.doi.org/10.1016/j.osn.2014.06.003}, url = {http://www.sciencedirect.com/science/article/pii/S1573427714000691}, author = {Eduardo Canale and Franco Robledo and Pablo Romero and Pablo Sartor}, } %%% RVR @ARTICLE{475978, author={Cancela, H. and El Khadiri, M.}, journal={Reliability, IEEE Transactions on}, title={A recursive variance-reduction algorithm for estimating communication-network reliability}, year={1995}, month={Dec}, volume={44}, number={4}, pages={595-602}, doi={10.1109/24.475978}, ISSN={0018-9529},} @book{rubino2009rare, title={Rare event simulation using {M}onte {C}arlo methods}, author={Rubino, G. and Tuffin, B.}, isbn={9780470772690}, lccn={2009004186}, year={2009}, publisher={Wiley} } @article{CancelaElKhadiri2003, author = {H'ector Cancela and Mohamed El Khadiri}, title = {The recursive variance-reduction simulation algorithm for network reliability evaluation}, journal = {IEEE Transactions on Reliability}, year = {2003}, volume = {52}, number = {2}, pages = {207-212}, } %% OTROS FUNDAMENTALES @article{Turing1936, author = {Turing, Alan}, citeulike-article-id = {321509}, journal = {Proceeding of the London Mathematical Society}, keywords = {computational-theory, historical}, posted-at = {2005-09-15 18:23:12}, priority = {2}, title = {{On computable numbers with an application to the {E}ntscheidungsproblem}}, year = {1936} } @book{george1996monte, title={Monte Carlo: }, author={George Fishman}, isbn={9780387945279}, lccn={97168075}, series={Springer Series in Operations Research and Financial Engineering}, year={1996}, publisher={Springer}, } @INPROCEEDINGS{Colbourn99reliabilityissues, author = {Charles J. Colbourn}, title = {Reliability Issues In Telecommunications Network Planning}, booktitle = {Telecommunications network planning, chapter 9}, year = {1999}, pages = {135--146}, publisher = {Kluwer Academic Publishers} } @article{Monmaetal, year={1990}, issn={0025-5610}, journal={Mathematical Programming}, volume={46}, number={1-3}, doi={10.1007/BF01585735}, title={Minimum-weight two-connected spanning networks}, publisher={Springer-Verlag}, keywords={Spanning networks; two-connectivity; traveling salesman problem}, author={Monma, ClydeL. and Munson, BethSpellman and Pulleyblank, WilliamR.}, pages={153-171}, language={English} }