Cover Image

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Conroy, Jonathan, Filtser, Arnold
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

On Strong Diameter Padded Decompositions
by: Filtser, Arnold
Published: (2019)

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

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

Dynamic Light Spanners in Doubling Metrics
by: Bhore, Sujoy, et al.
Published: (2026)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

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

Scattering and Sparse Partitions, and their Applications
by: Filtser, Arnold
Published: (2020)

Hop-Constrained Metric Embeddings and their Applications
by: Filtser, Arnold
Published: (2021)

A face cover perspective to $\ell_1$ embeddings of planar graphs
by: Filtser, Arnold
Published: (2019)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Highway Dimension: a Metric View
by: Feldmann, Andreas Emil, et al.
Published: (2024)

DAG Covers: The Steiner Point Effect
by: Bhore, Sujoy, et al.
Published: (2026)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
by: Filtser, Arnold, et al.
Published: (2026)

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

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

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
by: Bhore, Sujoy, et al.
Published: (2023)

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

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

A Separator for Minor-Free Graphs Beyond the Flow Barrier
by: Le, Hung
Published: (2026)

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

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

Clustering in Varying Metrics
by: Chakrabarty, Deeparnab, et al.
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)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
by: Alejandro-Soto, J. A., et al.
Published: (2025)

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

Individual Fairness in Graph Decomposition
by: Munagala, Kamesh, et al.
Published: (2024)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

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

Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors
by: Sharma, Roohani, et al.
Published: (2026)

Evaluating Optimal Safe Flows Decomposition for RNA Assembly
by: Ahmed, Bashar, et al.
Published: (2024)

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

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

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

Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
by: Chang, Yi-Jun
Published: (2023)

Induced Minors and Coarse Tree Decompositions
by: Chudnovsky, Maria, et al.
Published: (2026)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
by: Abboud, Amir, et al.
Published: (2023)

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

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