Max-Plus Objects to Study the Complexity of Graphs

Cristiano Bocci; Luca Chiantini; Fabio Rapallo

doi:10.1007/s11009-012-9311-x

Max-Plus Objects to Study the Complexity of Graphs

Cristiano Bocci
, Luca Chiantini
, Fabio Rapallo

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	507-525
Number of pages	19
Journal	Methodology and Computing in Applied Probability
Volume	16
Issue number	3
DOIs	https://doi.org/10.1007/s11009-012-9311-x
Publication status	Published - Sept 2014
Externally published	Yes

Keywords

Combinatorial central limit theorem
Complement graph
Matchings
Random permutations

Access to Document

10.1007/s11009-012-9311-x

Cite this

@article{7ee822dc5a94457e8cd97530917b0368,

title = "Max-Plus Objects to Study the Complexity of Graphs",

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 = "Combinatorial central limit theorem, Complement graph, Matchings, Random permutations",

author = "Cristiano Bocci and Luca Chiantini and Fabio Rapallo",

note = "Funding Information: Acknowledgement FR is supported by the Italian Ministry for Education, University and Research, grant PRIN 2009H8WPX5.",

year = "2014",

month = sep,

doi = "10.1007/s11009-012-9311-x",

language = "English",

volume = "16",

pages = "507--525",

journal = "Methodology and Computing in Applied Probability",

issn = "1387-5841",

publisher = "Springer",

number = "3",

}

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 -

Max-Plus Objects to Study the Complexity of Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this