Cover Image

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agassy, Daniel, Dorfman, Dani, Kaplan, Haim
Format:	Preprint
Published:	2022
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Expander Decomposition for Non-Uniform Vertex Measures
by: Agassy, Daniel, et al.
Published: (2025)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

Faster All-Pairs Optimal Electric Car Routing
by: Dorfman, Dani, et al.
Published: (2025)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

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

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

Expander Decomposition with Almost Optimal Overhead
by: Bansal, Nikhil, et al.
Published: (2026)

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

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

Minimum-cost paths for electric cars
by: Dorfman, Dani, et al.
Published: (2024)

New Structures and Algorithms for Length-Constrained Expander Decompositions
by: Haeupler, Bernhard, et al.
Published: (2024)

Faster Weak Expander Decompositions and Approximate Max Flow
by: Fleischmann, Henry, et al.
Published: (2025)

Expander Hierarchies for Normalized Cuts on Graphs
by: Hanauer, Kathrin, et al.
Published: (2024)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
by: Sadeh, Yaniv, et al.
Published: (2026)

Caching Connections in Matchings
by: Sadeh, Yaniv, et al.
Published: (2023)

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

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

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
by: Haeupler, Bernhard, et al.
Published: (2025)

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

Dynamic Edge Coloring of Forests
by: Kaplan, Haim, et al.
Published: (2026)

Search Trees on Trees via LP
by: Sadeh, Yaniv, et al.
Published: (2025)

Finding $b$-colorings Using Feedback Edges
by: Balabán, Jakub
Published: (2025)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
by: Aamand, Anders, et al.
Published: (2025)

Finding Colorings in One-Sided Expanders
by: Buhai, Rares-Darius, et al.
Published: (2025)

Expanderizing Higher Order Random Walks
by: Alev, Vedat Levi, et al.
Published: (2024)

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

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

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
by: Zhao, Yibin
Published: (2025)

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
by: Beretta, Lorenzo, et al.
Published: (2025)

On Differentially Private Linear Algebra
by: Kaplan, Haim, et al.
Published: (2024)

A Little Clairvoyance Is All You Need
by: Gupta, Anupam, et al.
Published: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by: Abboud, Amir, et al.
Published: (2024)

Adaptive Hashing: Faster Hash Functions with Fewer Collisions
by: Melis, Gábor
Published: (2026)

A Cut-Matching Game for Constant-Hop Expanders
by: Haeupler, Bernhard, et al.
Published: (2022)

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

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

Exploring Temporal Graphs with Frequent and Regular Edges
by: Adamson, Duncan
Published: (2025)

Spectral Clustering with Side Information
by: Fichtenberger, Hendrik, et al.
Published: (2025)

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