Multi-way sparsest cut problem on trees with a control on the number of parts and outliers

DOI10.1016/j.dam.2020.11.013zbMath1470.68060arXiv1702.05570MaRDI QIDQ2217481

Ramin Javadi, Saleh Ashkboos

Publication date: 29 December 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexity; Cheeger constant; graph partitioning; isoperimetric number; weighted trees; sparsest cut problem; normalized cut

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C22: Signed and weighted graphs