An Exact Polynomial Algorithm for the Outerplanar Facility Location Problem with Improved Time Complexity

被引：0

作者：

Gimadi, Edward ^{[1
,2
]}

机构：

[1] Sobolev Inst Math, 4 Koptyuga Av, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, 2 Pirogova Str, Novosibirsk 630090, Russia

来源：

ANALYSIS OF IMAGES, SOCIAL NETWORKS AND TEXTS, AIST 2017 | 2018年 / 10716卷

基金：

俄罗斯科学基金会;

关键词：

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

D O I：

10.1007/978-3-319-73013-4_27

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Unbounded Facility Location Problem on outerplanar graphs is considered. The algorithm with time complexity 0(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.

引用

页码：295 / 303

页数：9

共 14 条

[1]

Ageev A. A., 1989, UPRAVLYAEMYE SISTEMY, V29, P3

[2]

Ageev A.A., 1990, UPRAVLIAEMIE SYSTEMY, P3

[3]

[Anonymous], 2015, International Journal of Social Behavioral, Educational, Economic, Business and Industrial Engineering

[4]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness