### Abstract

A graph G=(V,E) satisfies the α,β-cut-property if the fraction of edges present in each cut of the graph lies between α and β. The Erdős-Rényi random graph G(n,p) satisfies this property w.h.p. for α=(1-ε)p and β=(1+ε)p whenever p is sufficiently large and ε is a suitably chosen constant.

We study the behavior of random shortest path metrics applied to graphs G that satisfy the α,β-cut-property. These random metrics are defined as follows: Let w(e) be independently drawn random edge weights for all e in E, and define d(u,v) to be the shortest path distance between u and v in G with respect to the weights w.

Using the ideas of Bringmann et al. (Algorithmica, 2015), who studied random shortest path metrics on the complete graph, i.e., the graph that satisfies the 1,1-cut-propertym we derive some properties of the metric and obtain a clustering of the vertices. Using this, we conduct a probabilistic analysis of some simple heuristics on these random shortest path metrics.

We study the behavior of random shortest path metrics applied to graphs G that satisfy the α,β-cut-property. These random metrics are defined as follows: Let w(e) be independently drawn random edge weights for all e in E, and define d(u,v) to be the shortest path distance between u and v in G with respect to the weights w.

Using the ideas of Bringmann et al. (Algorithmica, 2015), who studied random shortest path metrics on the complete graph, i.e., the graph that satisfies the 1,1-cut-propertym we derive some properties of the metric and obtain a clustering of the vertices. Using this, we conduct a probabilistic analysis of some simple heuristics on these random shortest path metrics.

Original language | English |
---|---|

Pages | 147-150 |

Publication status | Published - Jun 2018 |

Event | 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 - CNAM, Paris, France Duration: 18 Jun 2018 → 20 Jun 2018 Conference number: 16 http://ctw18.lipn.univ-paris13.fr/ |

### Workshop

Workshop | 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018 |
---|---|

Abbreviated title | CTW 2018 |

Country | France |

City | Paris |

Period | 18/06/18 → 20/06/18 |

Internet address |

### Keywords

- Random shortest paths
- Random metrics
- Approximation algorithms
- Erdős-Rényi random graph

## Fingerprint Dive into the research topics of 'Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics'. Together they form a unique fingerprint.

## Cite this

Klootwijk, S., Manthey, B., & Visser, S. K. (2018).

*Probabilistic Analysis of Optimization Problems on Generalized Random Shortest Path Metrics*. 147-150. Paper presented at 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2018, Paris, France.