アイテム詳細

登録内容を編集

このアイテムの新しいバージョンが利用可能です:
https://pure.mpg.de/pubman/item/item_2460729_4

このアイテムは取り下げられました。詳細要約

取り下げ

成果報告書

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

There are no locators available

Fulltext (restricted access)

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

フルテキスト (公開)

(アクセスなし)

付随資料 (公開)

There is no public supplementary material available

引用

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

要旨

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.