Optimal cuts and partitions in tree metrics in polynomial time
From MaRDI portal
Publication:396629
DOI10.1016/j.ipl.2013.03.009zbMath1358.05231arXiv1212.3471MaRDI 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
computational complexity; polynomial time; tree metric; geometric metric; optimal bisection; optimal cut
05C05: Trees
90C39: Dynamic programming
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
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