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.05570OpenAlexW3108022387MaRDI QIDQ2217481

Saleh Ashkboos, Ramin Javadi

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 complexityCheeger constantgraph partitioningisoperimetric numberweighted treessparsest cut problemnormalized cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (1)

Mean isoperimetry with control on outliers: exact and approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• On the complexity of isoperimetric problems on trees
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Clustering and outlier detection using isoperimetric number of trees
• On the isoperimetric spectrum of graphs and its approximations
• Eigenvalues and expanders
• On the hardness of approximating Multicut and Sparsest-Cut
• Isoperimetric numbers of graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Expander graphs and their applications
• Isoperimetric constants and the first eigenvalue of a compact riemannian manifold
• Approximation Algorithm for Sparsest k-Partitioning
• Multi-way spectral partitioning and higher-order cheeger inequalities
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Data Clustering: Theory, Algorithms, and Applications
• Expander flows, geometric embeddings and graph partitioning
• Geometry and spectra of compact Riemann surfaces

This page was built for publication: Multi-way sparsest cut problem on trees with a control on the number of parts and outliers