Imagen de Portada

On Approximating Cutwidth and Pathwidth

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Bansal, Nikhil, Katzelnick, Dor, Schwartz, Roy
Formato:	Preprint
Publicado:	2023
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Cutwidth and Crossings
por: Rauch, Johannes, et al.
Publicado: (2025)

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

Cutwidth Bounds via Vertex Partitions
por: Amarilli, Antoine, et al.
Publicado: (2025)

The Primal Pathwidth SETH
por: Lampis, Michael
Publicado: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

First Order Logic on Pathwidth Revisited Again
por: Lampis, Michael
Publicado: (2022)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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