Optimal cuts and partitions in tree metrics in polynomial time
(2013) In Information Processing Letters 113(12). p.447-451- Abstract
- We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one-dimensional geometric metric settings. Our method of solution could be also of independent interest in other applications. We discuss also an extension of our method to the class of metrics induced by the bounded treewidth graphs. (C) 2013 Elsevier B.V. All rights reserved.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3932383
- author
- Karpinski, Marek ; Lingas, Andrzej LU and Sledneu, Dzmitry LU
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Computational complexity, Optimal cut, Optimal bisection, Tree metric, Geometric metric, Polynomial time
- in
- Information Processing Letters
- volume
- 113
- issue
- 12
- pages
- 447 - 451
- publisher
- Elsevier
- external identifiers
-
- wos:000318834900010
- scopus:84876138482
- ISSN
- 0020-0190
- DOI
- 10.1016/j.ipl.2013.03.009
- language
- English
- LU publication?
- yes
- id
- 10b9bb96-d5fb-4bf3-a2bf-c1b42a87ab7b (old id 3932383)
- date added to LUP
- 2016-04-01 13:23:21
- date last changed
- 2022-01-27 18:57:34
@article{10b9bb96-d5fb-4bf3-a2bf-c1b42a87ab7b, abstract = {{We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one-dimensional geometric metric settings. Our method of solution could be also of independent interest in other applications. We discuss also an extension of our method to the class of metrics induced by the bounded treewidth graphs. (C) 2013 Elsevier B.V. All rights reserved.}}, author = {{Karpinski, Marek and Lingas, Andrzej and Sledneu, Dzmitry}}, issn = {{0020-0190}}, keywords = {{Computational complexity; Optimal cut; Optimal bisection; Tree metric; Geometric metric; Polynomial time}}, language = {{eng}}, number = {{12}}, pages = {{447--451}}, publisher = {{Elsevier}}, series = {{Information Processing Letters}}, title = {{Optimal cuts and partitions in tree metrics in polynomial time}}, url = {{http://dx.doi.org/10.1016/j.ipl.2013.03.009}}, doi = {{10.1016/j.ipl.2013.03.009}}, volume = {{113}}, year = {{2013}}, }