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.
Max-Plus Objects to Study the Complexity of Graphs
RAPALLO, Fabio
2014-01-01
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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
10.1007_s11009-012-9311-x.pdf
file disponibile solo agli amministratori
Tipologia:
Documento in Post-print
Licenza:
DRM non definito
Dimensione
822.05 kB
Formato
Adobe PDF
|
822.05 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
