### Abstract

The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity O(nm^{3}) was known for solving this problem, where n is the number of vertices, m is the number of possible plant locations. Using some properties of maximal outerplanar graphs (binary 2-trees) and the existence of an optimal solution with a family of centrally-connected service areas, the recurrence relations are obtained allowing to design an algorithm which can solve the problem in O(nm^{2.5}) time.

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

Title of host publication | Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers |

Editors | WMP VanDerAalst, DI Ignatov, M Khachay, SO Kuznetsov, Lempitsky, IA Lomazova, N Loukachevitch, A Napoli, A Panchenko, PM Pardalos, AV Savchenko, S Wasserman |

Publisher | Springer-Verlag GmbH and Co. KG |

Pages | 295-303 |

Number of pages | 9 |

ISBN (Print) | 9783319730127 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 - Moscow, Russian Federation Duration: 27 Jul 2017 → 29 Jul 2017 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 10716 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 |
---|---|

Country | Russian Federation |

City | Moscow |

Period | 27.07.2017 → 29.07.2017 |

### Keywords

- Dynamic programming
- Exact algoritm
- Outerplanar graph
- Time complexity
- Time complexity Dynamic programming
- TREES

## Fingerprint Dive into the research topics of 'An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity'. Together they form a unique fingerprint.

## Cite this

Gimadi, E. (2018). An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. In WMP. VanDerAalst, DI. Ignatov, M. Khachay, SO. Kuznetsov, Lempitsky, IA. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, PM. Pardalos, AV. Savchenko, & S. Wasserman (Eds.),

*Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers*(pp. 295-303). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-73013-4_27