Cover Image

A Separator for Minor-Free Graphs Beyond the Flow Barrier

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Le, Hung
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

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

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

Multiplicative Spanners in Minor-Free Graphs
by: Bodwin, Greg, et al.
Published: (2025)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
by: Kumar, Akash, et al.
Published: (2026)

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs
by: Conroy, Jonathan, et al.
Published: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

New weighted additive spanners
by: La, An, et al.
Published: (2024)

Distance Approximating Minors for Planar and Minor-Free Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

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

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
by: Chang, Hsien-Chih, 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)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
by: Kolmogorov, Vladimir, et al.
Published: (2026)

Listing Even Cycles Faster than the Submodular-Width Barrier
by: Nakos, Vasileios, et al.
Published: (2026)

The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
by: Chauhan, Archit, et al.
Published: (2024)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Distances in Planar Graphs are Almost for Free!
by: Mozes, Shay, et al.
Published: (2026)

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
by: Bai, Tian, et al.
Published: (2022)

RSVP: Beyond Weisfeiler Lehman Graph Isomorphism Test
by: Dutta, Sourav, et al.
Published: (2024)

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
by: Chang, Hsien-Chih, et al.
Published: (2024)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

Succinct Planar Encoding with Minor Operations
by: Kammer, Frank, et al.
Published: (2023)

Tree-Like Shortcuttings of Trees
by: Le, Hung, et al.
Published: (2025)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
by: Filtser, Arnold
Published: (2024)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
by: Ahi, Mridul, et al.
Published: (2025)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
by: Das, Syamantak, et al.
Published: (2024)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

Dichotomies for Tree Minor Containment with Structural Parameters
by: Gima, Tatsuya, et al.
Published: (2023)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
by: Jiang, Tianle, et al.
Published: (2024)

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)

Dynamic Locality Sensitive Orderings in Doubling Metrics
by: La, An, et al.
Published: (2024)

Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
by: Lindermayr, Alexander, et al.
Published: (2026)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
by: Dong, Sally, et al.
Published: (2023)

Fast In-Spectrum Graph Watermarks
by: Bourrée, Jade Garcia, et al.
Published: (2025)

Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation
by: Lu, Shangqi, et al.
Published: (2025)