Cover Image

Linear-Time Multilevel Graph Partitioning via Edge Sparsification

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gottesbüren, Lars, Maas, Nikolai, Rosch, Dominik, Sanders, Peter, Seemaier, Daniel
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tera-Scale Multilevel Graph Partitioning
by: Salwasser, Daniel, et al.
Published: (2024)

Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning
by: Sanders, Peter, et al.
Published: (2024)

Partitioning Trillion Edge Graphs on Edge Devices
by: Chhabra, Adil, et al.
Published: (2024)

Buffered Streaming Edge Partitioning
by: Chhabra, Adil, et al.
Published: (2024)

Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search
by: Gottesbüren, Lars, et al.
Published: (2024)

Engineering Optimal Parallel Task Scheduling
by: Akram, Matthew, et al.
Published: (2024)

Parallel Unconstrained Local Search for Partitioning Irregular Graphs
by: Maas, Nikolai, et al.
Published: (2023)

High-Quality Multi-Constraint Hypergraph Partitioning via Greedy Rebalancing
by: Maas, Nikolai
Published: (2026)

Fast and Faithful Edge Bundling using Spectral Sparsification
by: Jiang, Xingjue, et al.
Published: (2026)

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

Eulerian Graph Sparsification by Effective Resistance Decomposition
by: Jambulapati, Arun, et al.
Published: (2024)

Bootstrapping Dynamic APSP via Sparsification
by: Kyng, Rasmus, et al.
Published: (2024)

Adaptive Sparsification for Linear Programming
by: Objois, Étienne, et al.
Published: (2025)

Capacitated Partition Vertex Cover and Partition Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
by: He, Kaiwen, et al.
Published: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Weighted Partition Vertex and Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
by: Cohen-Addad, Vincent, et al.
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)

Scalable Multilevel and Memetic Signed Graph Clustering
by: Hausberger, Felix, et al.
Published: (2022)

Graph Partitioning With Limited Moves
by: Behbahani, Majid, et al.
Published: (2024)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Fully Dynamic Spectral Sparsification of Hypergraphs
by: Goranci, Gramoz, et al.
Published: (2025)

Max-Distance Sparsification for Diversification and Clustering
by: Kumabe, Soh
Published: (2024)

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
by: Forster, Sebastian, et al.
Published: (2025)

Balancing Weights, Directed Sparsification, and Augmenting Paths
by: Li, Jason
Published: (2026)

Efficient Algorithms and New Characterizations for CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2024)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
by: Kenneth, Yotam, et al.
Published: (2023)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
by: Assadi, Sepehr, et al.
Published: (2025)

Stochastic Matching via Local Sparsification
by: Ahmadian, Sara, et al.
Published: (2026)

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

Bellman-Ford in Almost-Linear Time for Dense Graphs
by: Li, George Z., et al.
Published: (2026)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

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

Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication
by: Ahrens, Willow
Published: (2020)