de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Decomposition of Trees and Paths via Correlation

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons201523

Lange,  Jan-Hendrik
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons98382

Andres,  Bjoern
Computer Vision and Multimodal Computing, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1706.06822.pdf
(Preprint), 237KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Lange, J.-H., & Andres, B. (2017). Decomposition of Trees and Paths via Correlation. Retrieved from http://arxiv.org/abs/1706.06822.


Cite as: http://hdl.handle.net/11858/00-001M-0000-002D-8B34-3
Abstract
We study the problem of decomposing (clustering) a tree with respect to costs attributed to pairs of nodes, so as to minimize the sum of costs for those pairs of nodes that are in the same component (cluster). For the general case and for the special case of the tree being a star, we show that the problem is NP-hard. For the special case of the tree being a path, we show (i) the objective function is not necessarily submodular, (ii) the problem can be solved in quasi-polynomial time by divide-and-conquer, (iii) the problem can be solved in polynomial time by polyhedral optimization techniques. To establish (iii), we offer a totally dual integral (TDI) description of path partition polytopes.