Advanced

Optimal cuts and partitions in tree metrics in polynomial time

Karpinski, Marek; Lingas, Andrzej LU and Sledneu, Dzmitry LU (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:
author
organization
publishing date
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
2013-07-15 12:22:04
date last changed
2018-05-29 10:52:16
@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},
  keyword      = {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},
  volume       = {113},
  year         = {2013},
}