### Abstract

We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. Algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval with positive ends. Sufficient conditions of asymptotic optimality are presented.

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

Title of host publication | Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers |

Editors | Igor Bykadorov, Vitaly Strusevich, Tatiana Tchemisova |

Publisher | Springer Gabler |

Pages | 30-38 |

Number of pages | 9 |

ISBN (Print) | 9783030333935 |

DOIs | |

Publication status | Published - 1 Jan 2019 |

Event | 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Russian Federation Duration: 8 Jul 2019 → 12 Jul 2019 |

### Publication series

Name | Communications in Computer and Information Science |
---|---|

Volume | 1090 CCIS |

ISSN (Print) | 1865-0929 |

ISSN (Electronic) | 1865-0937 |

### Conference

Conference | 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 |
---|---|

Country | Russian Federation |

City | Ekaterinburg |

Period | 08.07.2019 → 12.07.2019 |

### Keywords

- Asymptotically optimal algorithm
- Graph
- Minimum spanning tree
- Performance guarantees
- Probabilistic analysis
- Random inputs
- Uniform

## Fingerprint Dive into the research topics of 'On Given Diameter MST Problem on Random Input Data'. Together they form a unique fingerprint.

## Cite this

Gimadi, E. K., & Shin, E. Y. (2019). On Given Diameter MST Problem on Random Input Data. In I. Bykadorov, V. Strusevich, & T. Tchemisova (Eds.),

*Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Revised Selected Papers*(pp. 30-38). (Communications in Computer and Information Science; Vol. 1090 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-33394-2_3