Copertina

Optimal Padded Decomposition For Bounded Treewidth Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Filtser, Arnold, Friedrich, Tobias, Issac, Davis, Kumar, Nikhil, Le, Hung, Mallek, Nadym, Zeif, Ziena
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Discrete Mathematics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Hop-Constrained Metric Embeddings and their Applications
di: Filtser, Arnold
Pubblicazione: (2021)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
di: Abbasi, Ali, et al.
Pubblicazione: (2026)

Treewidth Parameterized by Feedback Vertex Number
di: Molter, Hendrik, et al.
Pubblicazione: (2025)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
di: Mallek, Nadym, et al.
Pubblicazione: (2025)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
di: Deligkas, Argyrios, et al.
Pubblicazione: (2025)

An Approximate Generalization of the Okamura-Seymour Theorem
di: Kumar, Nikhil
Pubblicazione: (2022)

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

An Improved Bound for the Beck-Fiala Conjecture
di: Bansal, Nikhil, et al.
Pubblicazione: (2025)

On Strong Diameter Padded Decompositions
di: Filtser, Arnold
Pubblicazione: (2019)

Temporal Graph Realization With Bounded Stretch
di: Mertzios, George B., et al.
Pubblicazione: (2025)

Online Graph Balancing and the Power of Two Choices
di: Bansal, Nikhil, et al.
Pubblicazione: (2026)

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

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2023)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
di: Paul-Pena, Daniel, et al.
Pubblicazione: (2024)

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

Optimal and Efficient Partite Decompositions of Hypergraphs
di: Krapivin, Andrew, et al.
Pubblicazione: (2025)

Optimal Enumeration of Eulerian Trails in Directed Graphs
di: Bals, Ben, et al.
Pubblicazione: (2026)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
di: Gahlawat, Harmender, et al.
Pubblicazione: (2025)

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

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
di: Dutta, Kunal, et al.
Pubblicazione: (2026)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
di: Mömke, Tobias, et al.
Pubblicazione: (2024)

Ranking with Multiple Objectives
di: Devanur, Nikhil R., et al.
Pubblicazione: (2024)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
di: de Montgolfier, Fabien, et al.
Pubblicazione: (2025)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
di: Bansal, Nikhil, et al.
Pubblicazione: (2025)

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

Bounding Width on Graph Classes of Constant Diameter
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
di: Liao, Meihao, et al.
Pubblicazione: (2025)

Twice-Ramanujan Sparsifiers
di: Batson, Joshua, et al.
Pubblicazione: (2008)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
di: Beisegel, Jesse, et al.
Pubblicazione: (2025)

Cutwidth Bounds via Vertex Partitions
di: Amarilli, Antoine, et al.
Pubblicazione: (2025)

Nearly Tight Bounds on Testing of Metric Properties
di: Bao, Yiqiao, et al.
Pubblicazione: (2024)

Bounding $\varepsilon$-scatter dimension via metric sparsity
di: Bourneuf, Romain, et al.
Pubblicazione: (2024)

Correcting matrix products over the ring of integers
di: Wu, Yu-Lun, et al.
Pubblicazione: (2023)

The Squishy Grid Problem
di: Cai, Zixi, et al.
Pubblicazione: (2025)

Approximation Algorithms for Optimal Hopsets
di: Dinitz, Michael, et al.
Pubblicazione: (2025)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
di: Swamy, Chaitanya, et al.
Pubblicazione: (2025)

Online Graph Coloring for $k$-Colorable Graphs
di: Kawarabayashi, Ken-ichi, et al.
Pubblicazione: (2025)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
di: Gaikwad, Ajinkya
Pubblicazione: (2025)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
di: Klimm, Max, et al.
Pubblicazione: (2022)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
di: Bentert, Matthias, et al.
Pubblicazione: (2026)