Cover Image

On Approximating Cutwidth and Pathwidth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bansal, Nikhil, Katzelnick, Dor, Schwartz, Roy
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
by: Casel, Katrin, et al.
Published: (2019)

Cutwidth and Crossings
by: Rauch, Johannes, et al.
Published: (2025)

Optimal 4-Approximation for the Correlated Pandora's Problem
by: Bansal, Nikhil, et al.
Published: (2025)

Cutwidth Bounds via Vertex Partitions
by: Amarilli, Antoine, et al.
Published: (2025)

The Primal Pathwidth SETH
by: Lampis, Michael
Published: (2024)

On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs
by: Aminian, Aida, et al.
Published: (2025)

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

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
by: Tale, Prafullkumar
Published: (2025)

Tight Bounds for some Classical Problems Parameterized by Cutwidth
by: Bojikian, Narek, et al.
Published: (2025)

A Tight Competitive Ratio for Online Submodular Welfare Maximization
by: Ganz, Amit, et al.
Published: (2023)

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
by: Bansal, Ishan, et al.
Published: (2022)

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

Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs
by: Nakamura, Kengo, et al.
Published: (2026)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

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

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

A Poisson Process for Submodular Maximization
by: Rozenman, Amit Ganz, et al.
Published: (2026)

A Global Analysis of the Primal-Dual Method for Pliable Families
by: Bansal, Ishan
Published: (2023)

Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four
by: Kaznatcheev, Artem, et al.
Published: (2024)

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

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

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

Warehouse Problem with Multiple Vendors and Generalized Complementarity Constraints
by: Bansal, Ishan, et al.
Published: (2024)

Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
by: Schwartz, Oded, et al.
Published: (2025)

Network Design on Undirected Series-Parallel Graphs
by: Bansal, Ishan, et al.
Published: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

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

Quasi-Monte Carlo Beyond Hardy-Krause
by: Bansal, Nikhil, et al.
Published: (2024)

Practical algorithms for Hierarchical overlap graphs
by: Talera, Saumya, et al.
Published: (2024)

Fault-Tolerant Bounded Flow Preservers
by: Bansal, Shivam, et al.
Published: (2024)

Approximating $δ$-Covering
by: Hartmann, Tim A., et al.
Published: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Polylogarithmic Approximation for Robust s-t Path
by: Li, Shi, et al.
Published: (2023)

The Impact of Approximation on Algorithmic Progress
by: Li, Jeffery, et al.
Published: (2026)

Hardness and Approximation for Coloring Digraphs
by: Chalermsook, Parinya, et al.
Published: (2026)

Girth Approximations in the CONGEST Model
by: Chechik, Shiri, et al.
Published: (2026)

Optimized 2-Approximation of Treewidth
by: Belbasi, Mahdi, et al.
Published: (2024)