@inproceedings{8fe382acd4b94815806c82fc5119e278,

title = "An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity",

abstract = "The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity O(nm3) 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(nm2.5) time.",

keywords = "Dynamic programming, Exact algoritm, Outerplanar graph, Time complexity, Time complexity Dynamic programming, TREES",

author = "Edward Gimadi",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-73013-4_27",

language = "English",

isbn = "9783319730127",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag GmbH and Co. KG",

pages = "295--303",

editor = "WMP VanDerAalst and DI Ignatov and M Khachay and SO Kuznetsov and Lempitsky and IA Lomazova and N Loukachevitch and A Napoli and A Panchenko and PM Pardalos and AV Savchenko and S Wasserman",

booktitle = "Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers",

address = "Germany",

note = "6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017 ; Conference date: 27-07-2017 Through 29-07-2017",

}