Cover Image

Cutwidth Bounds via Vertex Partitions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Amarilli, Antoine, Groz, Benoît
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
by: German, Samuel
Published: (2026)

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

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
by: Berthe, Gaétan, et al.
Published: (2024)

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
by: Komusiewicz, Christian, et al.
Published: (2026)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

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

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)

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

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

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

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

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
by: Shook, James M., et al.
Published: (2025)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

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

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

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

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

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

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

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

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

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

Sampling Tree-Weighted Partitions Without Sampling Trees
by: Cannon, Sarah, et al.
Published: (2025)

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

The Complexity of Cluster Vertex Splitting and Company
by: Firbas, Alexander, et al.
Published: (2023)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
by: Harada, Tsubasa
Published: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
by: Arndt, Stephen, et al.
Published: (2026)

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

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

Eternal Vertex Cover on Bipartite and Co-Bipartite Graphs
by: Misra, Neeldhara, et al.
Published: (2022)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
by: Foucaud, Florent, et al.
Published: (2024)

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

Tight Bounds for Sparsifying Random CSPs
by: Brakensiek, Joshua, et al.
Published: (2025)

Discrepancy Minimization via Regularization
by: Pesenti, Lucas, et al.
Published: (2022)

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

A Tight Bound on Localization of Electrical Flows
by: Gurel-Gurevich, Ori, et al.
Published: (2026)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)