Copertina

On Approximating Cutwidth and Pathwidth

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bansal, Nikhil, Katzelnick, Dor, Schwartz, Roy
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Cutwidth and Crossings
di: Rauch, Johannes, et al.
Pubblicazione: (2025)

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

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

The Primal Pathwidth SETH
di: Lampis, Michael
Pubblicazione: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

First Order Logic on Pathwidth Revisited Again
di: Lampis, Michael
Pubblicazione: (2022)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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