Max-Plus Objects to Study the Complexity of Graphs |
| |
| Authors: | Cristiano Bocci Luca Chiantini Fabio Rapallo |
| |
| Institution: | 1. Dipartimento di Scienze Matematiche e Informatiche “R. Magari”, Università di Siena, Pian dei Mantellini 44, 53100, Siena, Italy
2. Dipartimento di Scienze e Innovazione Tecnologica, Università del Piemonte Orientale, Viale Teresa Michel 11, 15121, Alessandria, Italy
|
| |
| Abstract: | Given an undirected graph G, we define a new object H G , called the mp-chart of G, in the max-plus algebra. We use it, together with the max-plus permanent, to describe the complexity of graphs. We show how to compute the mean and the variance of H G in terms of the adjacency matrix of G and we give a central limit theorem for H G . Finally, we show that the mp-chart is easily tractable also for the complement graph. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
