On the complexity of isoperimetric problems on trees

DOI10.1016/j.dam.2011.08.015zbMath1237.05042arXiv1009.0706MaRDI QIDQ765346

Ramin Javadi, Amir Daneshgar

Publication date: 19 March 2012

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

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

zbMATH Keywords

computational complexity; Cheeger constant; graph partitioning; approximation algorithms; isoperimetric number; weighted trees; normalized cut

Mathematics Subject Classification ID

05C05: Trees

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

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms