Optimal cuts and partitions in tree metrics in polynomial time

DOI10.1016/J.IPL.2013.03.009zbMATH Open1358.05231arXiv1212.3471OpenAlexW2963095783MaRDI QIDQ396629FDOQ396629

Authors: Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu 

Publication date: 13 August 2014

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

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.

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

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

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)

Cites Work

• Approximation algorithms for NP-hard problems.
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Title not available (Why is that?)
• Title not available (Why is that?)
• A tight bound on approximating arbitrary metrics by tree metrics
• Spectral methods for matrices and tensors
• Random sampling and approximation of MAX-CSPs
• Tensor decomposition and approximation schemes for constraint satisfaction problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation schemes for metric bisection and partitioning

Cited In (2)

• 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)