Image de couverture de livre

On Approximating Cutwidth and Pathwidth

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bansal, Nikhil, Katzelnick, Dor, Schwartz, Roy
Format:	Preprint
Publié:	2023
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
par: Casel, Katrin, et autres
Publié: (2019)

Cutwidth and Crossings
par: Rauch, Johannes, et autres
Publié: (2025)

Optimal 4-Approximation for the Correlated Pandora's Problem
par: Bansal, Nikhil, et autres
Publié: (2025)

Cutwidth Bounds via Vertex Partitions
par: Amarilli, Antoine, et autres
Publié: (2025)

The Primal Pathwidth SETH
par: Lampis, Michael
Publié: (2024)

On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs
par: Aminian, Aida, et autres
Publié: (2025)

Expander Decomposition with Almost Optimal Overhead
par: Bansal, Nikhil, et autres
Publié: (2026)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
par: Bansal, Nikhil, et autres
Publié: (2026)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
par: Tale, Prafullkumar
Publié: (2025)

Tight Bounds for some Classical Problems Parameterized by Cutwidth
par: Bojikian, Narek, et autres
Publié: (2025)

A Tight Competitive Ratio for Online Submodular Welfare Maximization
par: Ganz, Amit, et autres
Publié: (2023)

Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
par: Bansal, Ishan, et autres
Publié: (2022)

An Approximate Generalization of the Okamura-Seymour Theorem
par: Kumar, Nikhil
Publié: (2022)

Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs
par: Nakamura, Kengo, et autres
Publié: (2026)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
par: Greilhuber, Jakob, et autres
Publié: (2026)

An Improved Bound for the Beck-Fiala Conjecture
par: Bansal, Nikhil, et autres
Publié: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
par: Bansal, Nikhil, et autres
Publié: (2024)

First Order Logic on Pathwidth Revisited Again
par: Lampis, Michael
Publié: (2022)

A Poisson Process for Submodular Maximization
par: Rozenman, Amit Ganz, et autres
Publié: (2026)

A Global Analysis of the Primal-Dual Method for Pliable Families
par: Bansal, Ishan
Publié: (2023)

Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four
par: Kaznatcheev, Artem, et autres
Publié: (2024)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
par: Bansal, Nikhil, et autres
Publié: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
par: Fei, Yumou, et autres
Publié: (2025)

Online Graph Balancing and the Power of Two Choices
par: Bansal, Nikhil, et autres
Publié: (2026)

Warehouse Problem with Multiple Vendors and Generalized Complementarity Constraints
par: Bansal, Ishan, et autres
Publié: (2024)

Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
par: Schwartz, Oded, et autres
Publié: (2025)

Network Design on Undirected Series-Parallel Graphs
par: Bansal, Ishan, et autres
Publié: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
par: Minzer, Dor, et autres
Publié: (2024)

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs
par: Das, Syamantak, et autres
Publié: (2024)

Quasi-Monte Carlo Beyond Hardy-Krause
par: Bansal, Nikhil, et autres
Publié: (2024)

Practical algorithms for Hierarchical overlap graphs
par: Talera, Saumya, et autres
Publié: (2024)

Fault-Tolerant Bounded Flow Preservers
par: Bansal, Shivam, et autres
Publié: (2024)

Approximating $δ$-Covering
par: Hartmann, Tim A., et autres
Publié: (2024)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2026)

Polylogarithmic Approximation for Robust s-t Path
par: Li, Shi, et autres
Publié: (2023)

The Impact of Approximation on Algorithmic Progress
par: Li, Jeffery, et autres
Publié: (2026)

Hardness and Approximation for Coloring Digraphs
par: Chalermsook, Parinya, et autres
Publié: (2026)

Girth Approximations in the CONGEST Model
par: Chechik, Shiri, et autres
Publié: (2026)

Optimized 2-Approximation of Treewidth
par: Belbasi, Mahdi, et autres
Publié: (2024)