Graph algorithm based submodular function for sparsest cut problem

DOI10.1142/S0129054122460029MaRDI QIDQ6955231zbMATH OpenFDO

Authors Xiaoyan Zhang, Hong Chang, Longkun Guo, Donglei Du, Gaokai Zou, Yuanyuan Xiong

Publication date 23 July 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

sparsitybipartitionsubmodular functionsparsest cut problemprincipal partition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Expander graphs (05C48)

Cites work

• scientific article; zbMATH DE number 3914356 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• scientific article; zbMATH DE number 5785643 (Why is no real title available?)
• A framework for solving VLSI graph layout problems
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Applications of a Planar Separator Theorem
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximation algorithm for sparsest \(k\)-partitioning
• Eigenvalues and expanders
• Expander flows, geometric embeddings and graph partitioning
• Expander graphs and their applications
• Expanders obtained from affine transformations
• Improving graph partitions using submodular functions.
• Many sparse cuts via higher eigenvalues
• Maximum flow and minimum-cost flow in almost-linear time
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On Nonlinear Fractional Programming
• On clusterings: good, bad and spectral
• Sparsest cuts and bottlenecks in graphs
• Submodular functions and electrical networks
• Submodular functions and optimization
• The complexity of finding uniform sparsest cuts in various graph classes
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

This page was built for publication: Graph algorithm based submodular function for sparsest cut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6955231)