Item

ITEM ACTIONS

Please note that a newer version of this item is available:
https://pure.mpg.de/pubman/item/item_2460729_4

This item is discarded!DetailsSummary

Discarded

Paper

Decomposition of Trees and Paths via Correlation

MPS-Authors

/persons/resource/persons201523

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

/persons/resource/persons98382

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

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

(No access)

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.

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.