Cover Image

Expander Hierarchies for Normalized Cuts on Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Hanauer, Kathrin, Henzinger, Monika, Münk, Robin, Räcke, Harald, Vötsch, Maximilian
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
by: Henzinger, Monika, et al.
Published: (2025)

Efficient Contractions of Dynamic Graphs -- with Applications
by: Henzinger, Monika, et al.
Published: (2025)

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
by: El-Hayek, Antoine, et al.
Published: (2023)

Dynamic Demand-Aware Link Scheduling for Reconfigurable Datacenters
by: Hanauer, Kathrin, et al.
Published: (2023)

Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2025)

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2022)

Binned Group Algebra Factorization for Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2025)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Almost Tight Error Bounds on Differentially Private Continual Counting
by: Henzinger, Monika, et al.
Published: (2022)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
by: El-Hayek, Antoine, et al.
Published: (2024)

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
by: El-Hayek, Antoine, et al.
Published: (2025)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
by: Räcke, Harald, et al.
Published: (2024)

Making Old Things New: A Unified Algorithm for Differentially Private Clustering
by: la Tour, Max Dupré, et al.
Published: (2024)

Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning
by: Ghriss, Ayoub
Published: (2025)

Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
by: Peng, Pan, et al.
Published: (2025)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)

Improved Differentially Private Continual Observation Using Group Algebra
by: Henzinger, Monika, et al.
Published: (2024)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
by: Long, Yaowei, et al.
Published: (2024)

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

Differentially Private Algorithms for Graphs Under Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2021)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

Concurrent Composition for Differentially Private Continual Mechanisms
by: Henzinger, Monika, et al.
Published: (2024)

Optimal Electrical Oblivious Routing on Expanders
by: Florescu, Cella, et al.
Published: (2024)

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
by: Agassy, Daniel, et al.
Published: (2022)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
by: Chen, Daoyuan, et al.
Published: (2024)

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
by: la Tour, Max Dupré, et al.
Published: (2024)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Improved Lower Bounds for Privacy under Continual Release
by: Aryanfard, Bardiya, et al.
Published: (2025)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
by: Yang, Yichun, et al.
Published: (2024)

Learning Augmented Graph $k$-Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Incremental (k, z)-Clustering on Graphs
by: Cruciani, Emilio, et al.
Published: (2026)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

On the Streaming Complexity of Expander Decomposition
by: Chen, Yu, et al.
Published: (2024)

Dynamic Hierarchical $j$-Tree Decomposition and Its Applications
by: Goranci, Gramoz, et al.
Published: (2026)

Improved Directed Expander Decompositions
by: Fleischmann, Henry, et al.
Published: (2025)

GEFL: Extended Filtration Learning for Graph Classification
by: Zhang, Simon, et al.
Published: (2024)