Diameter in weighted random graphs

Marc Lelarge

Description

Diameter in weighted random graphs Marc Lelarge INRIA & ENS Joint work with Hamed Amini (INRIA & ENS) and Moez Draief (Imperial College London). Oberwolfach, October 2010. 1

• dn d?


• labeled half-edges


• maxi?v di


• ofg defined


• diameter ofg


• weighted diameter


• n? pk

Informations

• Publié par: pefav
• Nombre de lectures: 7
• Langue: English

Extrait

Diameter in weighted random graphs

Marc Lelarge

INRIA & ENS

Joint work with Hamed Amini (INRIA & ENS) and Moez Draief (Imperial College London).

Oberwolfach, October 2010.

1

Graph G = ( VE ) :

WEIGHTED DIAMETER

- Distance dist ( a b ) = min π ∈ Π( ab ) | π | , the number of edges in E in the shortest path connecting a and b .

- Diameter of G

denedyb:

diam ( G ) = max { dist ( a b )  a b ∈ V dist ( a b ) < ∞} 

- Weight associated to each edge e ∈ E : w e . - Weighted distance dist w ( a b ) = min π ∈ Π( ab ) P e ∈ π w e . - Weighted diameter of G dened by:

diam w ( G ) = max { dist w ( a b )  a b ∈ V dist w ( a b ) < ∞} 