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.
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/47502
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo