Optimal cuts and partitions in tree metrics in polynomial time

DOI10.1016/j.ipl.2013.03.009zbMath1358.05231arXiv1212.3471OpenAlexW2963095783MaRDI QIDQ396629

Andrzej Lingas, Marek Karpinski, 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 complexitypolynomial timetree metricgeometric metricoptimal bisectionoptimal cut

Mathematics Subject Classification ID

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

Cites Work

• Random sampling and approximation of MAX-CSPs
• Spectral methods for matrices and tensors
• Tensor decomposition and approximation schemes for constraint satisfaction problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A tight bound on approximating arbitrary metrics by tree metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item