Cover Image

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kolmogorov, Vladimir, Spalding-Jamieson, Jack
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
by: Spalding-Jamieson, Jack
Published: (2025)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
by: Arkhipov, Pavel, et al.
Published: (2026)

A computational study of Gomory-Hu construction tree algorithms
by: Kolmogorov, Vladimir
Published: (2022)

OrderedCuts: A new approach for computing Gomory-Hu tree
by: Kolmogorov, Vladimir
Published: (2022)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
by: Davies-Peck, Peter
Published: (2026)

Parameterized Algorithms for Minimum Sum Vertex Cover
by: Aute, Shubhada, et al.
Published: (2024)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
by: Lynch, Jayson, et al.
Published: (2025)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Faster algorithms for packing forests in graphs and related problems
by: Arkhipov, Pavel, et al.
Published: (2024)

Greedy matroid base packings with applications to dynamic graph density and orientations
by: Arkhipov, Pavel, et al.
Published: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
by: Chuzhoy, Julia, et al.
Published: (2025)

Connectivity-Preserving Minimum Separator in AT-free Graphs
by: Kenig, Batya
Published: (2025)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Simple parallel estimation of the partition ratio for Gibbs distributions
by: Harris, David G., et al.
Published: (2025)

New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs
by: Heck, Sophia, et al.
Published: (2026)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
by: Esmer, Barış Can, et al.
Published: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
by: Gupta, Sushmita, et al.
Published: (2024)

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
by: Lev-Ran, Asaf, et al.
Published: (2026)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
by: Kobayashi, Yusuke, et al.
Published: (2026)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

Improved Approximation Algorithm for Maximum Balanced Biclique
by: Manurangsi, Pasin
Published: (2026)

Hardness and Approximation Algorithms for Balanced Districting Problems
by: Dharangutte, Prathamesh, et al.
Published: (2025)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Balanced Partitioning for Optimizing Big Graph Computation: Complexities and Approximation Algorithms
by: Ning, Baoling, et al.
Published: (2024)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

A new notion of commutativity for the algorithmic Lovász Local Lemma
by: Harris, David G., et al.
Published: (2020)

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

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
by: Chuzhoy, Julia, et al.
Published: (2025)

Fast Algorithms for Minimum Homology Basis
by: Dhar, Amritendu, et al.
Published: (2021)

A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation
by: Crane, Alex, et al.
Published: (2026)

Addressing Bias in Algorithmic Solutions: Exploring Vertex Cover and Feedback Vertex Set
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
by: Bhore, Sujoy, et al.
Published: (2024)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
by: Hua, Kevin, et al.
Published: (2024)

New Algorithms for Incremental Minimum Spanning Trees and Temporal Graph Applications
by: Ding, Xiangyun, et al.
Published: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
by: Mosenzon, Ron
Published: (2025)