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)

Full work available at URL https://doi.org/10.1142/S0129054122460029

zbMATH Keywords

bipartitionprincipal partitionsparsest cut problemsparsitysubmodular function

Mathematics Subject Classification ID

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

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• 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
• 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?)
• 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 clusterings: good, bad and spectral
• On Nonlinear Fractional Programming
• 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

Cited in

(1)

• The budget-feasible mechanisms on non-monotone k-submodular objectives for the offline and online procurement auctions

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)