Standard
An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. / Gimadi, Edward.
Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. ed. / WMP VanDerAalst; DI Ignatov; M Khachay; SO Kuznetsov; Lempitsky; IA Lomazova; N Loukachevitch; A Napoli; A Panchenko; PM Pardalos; AV Savchenko; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. p. 295-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10716 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
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. 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, pp. 295-303, 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017, Moscow, Russian Federation,
27.07.2017.
https://doi.org/10.1007/978-3-319-73013-4_27
APA
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
Vancouver
Gimadi E.
An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. In VanDerAalst WMP, Ignatov DI, Khachay M, Kuznetsov SO, Lempitsky, Lomazova IA, Loukachevitch N, Napoli A, Panchenko A, Pardalos PM, Savchenko AV, Wasserman S, editors, Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2018. p. 295-303. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-73013-4_27
Author
Gimadi, Edward. /
An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity. Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers. editor / WMP VanDerAalst ; DI Ignatov ; M Khachay ; SO Kuznetsov ; Lempitsky ; IA Lomazova ; N Loukachevitch ; A Napoli ; A Panchenko ; PM Pardalos ; AV Savchenko ; S Wasserman. Springer-Verlag GmbH and Co. KG, 2018. pp. 295-303 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@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",
}
RIS
TY - GEN
T1 - An exact polynomial algorithm for the outerplanar facility location problem with improved time complexity
AU - Gimadi, Edward
PY - 2018/1/1
Y1 - 2018/1/1
N2 - 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.
AB - 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.
KW - Dynamic programming
KW - Exact algoritm
KW - Outerplanar graph
KW - Time complexity
KW - Time complexity Dynamic programming
KW - TREES
UR - http://www.scopus.com/inward/record.url?scp=85039416451&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-73013-4_27
DO - 10.1007/978-3-319-73013-4_27
M3 - Conference contribution
AN - SCOPUS:85039416451
SN - 9783319730127
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 295
EP - 303
BT - Analysis of Images, Social Networks and Texts - 6th International Conference, AIST 2017, Revised Selected Papers
A2 - VanDerAalst, WMP
A2 - Ignatov, DI
A2 - Khachay, M
A2 - Kuznetsov, SO
A2 - Lempitsky, null
A2 - Lomazova, IA
A2 - Loukachevitch, N
A2 - Napoli, A
A2 - Panchenko, A
A2 - Pardalos, PM
A2 - Savchenko, AV
A2 - Wasserman, S
PB - Springer-Verlag GmbH and Co. KG
T2 - 6th International Conference on Analysis of Images, Social Networks and Texts, AIST 2017
Y2 - 27 July 2017 through 29 July 2017
ER -
