TY - JOUR
T1 - Max-Plus Objects to Study the Complexity of Graphs
AU - Bocci, Cristiano
AU - Chiantini, Luca
AU - Rapallo, Fabio
N1 - Funding Information:
Acknowledgement FR is supported by the Italian Ministry for Education, University and Research, grant PRIN 2009H8WPX5.
PY - 2014/9
Y1 - 2014/9
N2 - 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.
AB - 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.
KW - Combinatorial central limit theorem
KW - Complement graph
KW - Matchings
KW - Random permutations
UR - https://www.scopus.com/pages/publications/84905221038
U2 - 10.1007/s11009-012-9311-x
DO - 10.1007/s11009-012-9311-x
M3 - Article
SN - 1387-5841
VL - 16
SP - 507
EP - 525
JO - Methodology and Computing in Applied Probability
JF - Methodology and Computing in Applied Probability
IS - 3
ER -