Abstract:
We model a communication system by a network, were the terminals are perfect but links may fail randomly, with identical probability q = 1-p. This defines a partial random network. The all-terminal reliability R(p) is the probability that this random graph is connected, and it is a polynomial in p. Finding the reliability polynomial can be reduced to a hard counting problem. © 2016 IEEE.
Registro:
| Documento: |
Conferencia
|
| Título: | Network utility problem and easy reliability polynomials |
| Autor: | Canale, E.; Romero, P.; Rubino, G.; Warnes, X.; Papadimitriou D.; Jonsson M.; Rak J.; Somani A.; Vinel A. |
| Filiación: | Facultad Politécnica, Universidad Nacional de Asunción, Ruta Mcal. Estigarribia, Km. 10, 5, San Lorenzo, Paraguay
Facultad de Ingenieriá, Universidad de la República, Julio Herrera y Reissig 565, Montevideo, Uruguay
Inria Rennes, Bretagne Atlantique, Campus de Beaulieu, Rennes Cedex, 35042, France
Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Intendente Guiraldes 2160, Buenos Aires, Argentina
|
| Palabras clave: | Polynomials; All terminal reliability; Counting problems; Network utility; Random graphs; Random network; Reliability polynomials; Reliability |
| Año: | 2016
|
| Página de inicio: | 79
|
| Página de fin: | 84
|
| DOI: |
http://dx.doi.org/10.1109/RNDM.2016.7608271 |
| Título revista: | 8th International Workshop on Resilient Networks Design and Modeling, RNDM 2016
|
| Título revista abreviado: | Proc. Int. Workshop Resilient Networks Des. Model., RNDM
|
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97814673_v_n_p79_Canale |
Referencias:
- Gilbert, E.N., Random graphs (1959) Annals of Mathematical Statistics, 30, pp. 1141-1144
- Ball, M.O., Computational complexity of network reliability analysis: An overview (1986) IEEE Transactions on Reliability, 35 (3), pp. 230-239. , aug
- Ball, M.O., Provan, J.S., The complexity of counting cuts and of computing the probability that a graph is connected (1983) SIAM J. Computing, 12, pp. 777-788
- Harary, F., (1994) Graph Theory Ser. Addison-Wesley Series in Mathematics, , Perseus Books
- Kirchoff, G., Ü ber die auflösung der gleichungen auf welche man bei der untersuchung der linearen verteilung galvanischer str öme geführt wird (1847) Ann. Phys. Chem., 72, pp. 497-508
- Biggs, N., (1993) Algebraic Graph Theory Ser. Cambridge Mathematical Li-brary, , Cambridge University Press
- Ford, L.R., Fulkerson, D.R., (1962) Flows in Networks, , Princeton University Press
- West, D.B., (2000) Introduction to Graph Theory, 2nd Ed, , Prentice Hall, September
- O'Neill, D., Goldsmith, A., Boyd, S., Wireless network utility max-imization (2008) MILCOM 2008-2008 IEEE Military Communications Conference, pp. 1-8. , Nov
- Kelly, F., Charging and rate control for elastic traffic (1997) European Transactions on Telecommunications, 8 (1), pp. 33-37
- Harary, F., The maximum connectivity of a graph (1962) Proceedings of the National Academy of Sciences, 48, pp. 1142-1146. , sepA4 -
Citas:
---------- APA ----------
Canale, E., Romero, P., Rubino, G., Warnes, X., Papadimitriou D., Jonsson M., Rak J.,..., Vinel A.
(2016)
. Network utility problem and easy reliability polynomials. 8th International Workshop on Resilient Networks Design and Modeling, RNDM 2016, 79-84.
http://dx.doi.org/10.1109/RNDM.2016.7608271---------- CHICAGO ----------
Canale, E., Romero, P., Rubino, G., Warnes, X., Papadimitriou D., Jonsson M., et al.
"Network utility problem and easy reliability polynomials"
. 8th International Workshop on Resilient Networks Design and Modeling, RNDM 2016
(2016) : 79-84.
http://dx.doi.org/10.1109/RNDM.2016.7608271---------- MLA ----------
Canale, E., Romero, P., Rubino, G., Warnes, X., Papadimitriou D., Jonsson M., et al.
"Network utility problem and easy reliability polynomials"
. 8th International Workshop on Resilient Networks Design and Modeling, RNDM 2016, 2016, pp. 79-84.
http://dx.doi.org/10.1109/RNDM.2016.7608271---------- VANCOUVER ----------
Canale, E., Romero, P., Rubino, G., Warnes, X., Papadimitriou D., Jonsson M., et al. Network utility problem and easy reliability polynomials. Proc. Int. Workshop Resilient Networks Des. Model., RNDM. 2016:79-84.
http://dx.doi.org/10.1109/RNDM.2016.7608271