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.
Bocci, C., Chiantini, L., Rapallo, F. (2014). Max-plus objects to study the complexity of graphs. METHODOLOGY AND COMPUTING IN APPLIED PROBABILITY, 16, 507-525 [10.1007/s11009-012-9311-x].
Max-plus objects to study the complexity of graphs
BOCCI, CRISTIANO;CHIANTINI, LUCA;
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 | Dimensione | Formato | |
|---|---|---|---|
|
2014.Grafi.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
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.
https://hdl.handle.net/11365/47502
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo