On the complexity of isoperimetric problems on trees

DOI10.1016/j.dam.2011.08.015zbMath1237.05042arXiv1009.0706OpenAlexW1655771767MaRDI 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 complexityCheeger constantgraph partitioningapproximation algorithmsisoperimetric numberweighted treesnormalized cut

Mathematics Subject Classification ID

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

Related Items

Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Clustering and outlier detection using isoperimetric number of trees ⋮ Multi-way sparsest cut problem on trees with a control on the number of parts and outliers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• Minimum cost subpartitions in graphs
• On the isoperimetric spectrum of graphs and its approximations
• Computing sharp bounds for hard clustering problems on trees
• Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
• Weighted graph Laplacians and isoperimetric inequalities
• The shifting algorithm technique for the partitioning of trees
• Isoperimetric numbers of graphs
• Succinct Representation of Balanced Parentheses and Static Trees
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Algorithmic Aspects of Graph Connectivity
• Graph Clustering and Minimum Cut Trees
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: On the complexity of isoperimetric problems on trees