Optimal cuts and partitions in tree metrics in polynomial time

DOI10.1016/J.IPL.2013.03.009MaRDI QIDQ396629zbMATH OpenOpenAlexFDO

Authors Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

Publication date 13 August 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.3471

zbMATH Keywords

computational complexitytree metricpolynomial timegeometric metricoptimal bisectionoptimal cut

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Parameterized algorithms for minimum tree cut/paste distance and minimum common integer partition
• Improved parameterized and exact algorithms for cut problems on trees
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Parameterized complexity of weighted multicut in trees
• Tree packing and approximating k-cuts
• On algorithms employing treewidth for L-bounded cut problems
• Min-cut partitioning on underlying tree and graph structures
• Parameterized complexity of multicut in weighted trees
• Efficient algorithms for generalized cut‐trees

Cites work

• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 1496577 (Why is no real title available?)
• scientific article; zbMATH DE number 1929926 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A tight bound on approximating arbitrary metrics by tree metrics
• Approximation algorithms for NP-hard problems.
• Approximation schemes for metric bisection and partitioning
• Capacitated metric labeling
• Random sampling and approximation of MAX-CSPs
• Spectral methods for matrices and tensors
• Tensor decomposition and approximation schemes for constraint satisfaction problems

Cited in

(3)

• Optimal partition of a tree with social distance
• Improved parameterized and exact algorithms for cut problems on trees
• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition

This page was built for publication: Optimal cuts and partitions in tree metrics in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396629)