Optimal cuts and partitions in tree metrics in polynomial time
type: Item
instance of: scholarly article
title: Optimal cuts and partitions in tree metrics in polynomial time
zbMATH Open document ID: 1358.05231
author: Marek Karpinski
author: Andrzej Lingas
author: Dzmitry Sledneu
published in: Information Processing Letters
publication date: 2014-08-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/1212.3471
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 6329888
zbMATH Keywords: computational complexity
zbMATH Keywords: optimal cut
zbMATH Keywords: optimal bisection
zbMATH Keywords: tree metric
zbMATH Keywords: geometric metric
zbMATH Keywords: polynomial time
MaRDI profile type: Publication
OpenAlex ID: W2963095783
arXiv ID: 1212.3471
cites work: Q3002852
cites work: Q5365095
cites work: Q3549709
cites work: Random sampling and approximation of MAX-CSPs
cites work: Tensor decomposition and approximation schemes for constraint satisfaction problems
cites work: Q5501299
cites work: Q4500688
cites work: Spectral methods for matrices and tensors
cites work: Q4708558
cites work: A tight bound on approximating arbitrary metrics by tree metrics
cites work: Q5315023
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
DOI: 10.1016/J.IPL.2013.03.009
Recommended article: Parameterized algorithms for minimum tree cut/paste distance and minimum common integer partition
Recommended article: Improved parameterized and exact algorithms for cut problems on trees
Recommended article: Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
Recommended article: Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
Recommended article: Parameterized complexity of weighted multicut in trees
Recommended article: Tree packing and approximating \(k\)-cuts
Recommended article: On Algorithms Employing Treewidth for $L$-bounded Cut Problems
Recommended article: Min-cut partitioning on underlying tree and graph structures
Recommended article: Parameterized complexity of multicut in weighted trees
Recommended article: Efficient algorithms for generalized cut‐trees
description: scientific article; zbMATH DE number 6329888