Buchumschlag

Separator Theorem for Minor-Free Graphs in Linear Time

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bonnet, Édouard, Korhonen, Tuukka, Le, Hung, Li, Jason, Masařík, Tomáš
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
von: Bonnet, Édouard, et al.
Veröffentlicht: (2023)

Coarse Balanced Separators in Fat-Minor-Free Graphs
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
von: Korhonen, Tuukka
Veröffentlicht: (2024)

Dynamic Treewidth in Logarithmic Time
von: Korhonen, Tuukka
Veröffentlicht: (2025)

A Separator for Minor-Free Graphs Beyond the Flow Barrier
von: Le, Hung
Veröffentlicht: (2026)

Minor Containment and Disjoint Paths in almost-linear time
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Connectivity augmentation is fixed-parameter tractable
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2026)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2025)

Dynamic Meta-Kernelization
von: Bertram, Christian, et al.
Veröffentlicht: (2025)

Stability in Graphs with Matroid Constraints
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Colouring $(P_r+P_s)$-Free Graphs
von: Klimošová, Tereza, et al.
Veröffentlicht: (2018)

Bellman-Ford in Almost-Linear Time for Dense Graphs
von: Li, George Z., et al.
Veröffentlicht: (2026)

Fixed-Parameter Tractability of Hedge Cut
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Multiplicative Spanners in Minor-Free Graphs
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Deterministic Mincut in Almost-Linear Time
von: Li, Jason
Veröffentlicht: (2021)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Computing Tree Decompositions with Small Independence Number
von: Dallard, Clément, et al.
Veröffentlicht: (2022)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

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

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
von: Kratochvíl, Jan, et al.
Veröffentlicht: (2020)

Network Unreliability in Almost-Linear Time
von: Cen, Ruoxu, et al.
Veröffentlicht: (2025)

Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs
von: Kumar, Akash, et al.
Veröffentlicht: (2026)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
von: Dvořák, Pavel, et al.
Veröffentlicht: (2022)

Unbreakable Decomposition in Close-to-Linear Time
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
von: Hušek, Radek, et al.
Veröffentlicht: (2020)

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

Packing Short Cycles
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
von: Hatzel, Meike, et al.
Veröffentlicht: (2022)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2022)

Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model
von: Jauregui, Benjamin, et al.
Veröffentlicht: (2018)

Deterministic Almost-Linear-Time Gomory-Hu Trees
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
von: Gottesbüren, Lars, et al.
Veröffentlicht: (2025)

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

A tight quasi-polynomial bound for Global Label Min-Cut
von: Jaffke, Lars, et al.
Veröffentlicht: (2022)

Coloring Hardness on Low Twin-Width Graphs
von: Bonnet, Édouard
Veröffentlicht: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
von: Marx, Dániel, et al.
Veröffentlicht: (2026)