Cover Image

Optimized 2-Approximation of Treewidth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Belbasi, Mahdi, Fürer, Martin, Kumar, Medha
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
by: Dong, Sally, et al.
Published: (2023)

Losing Treewidth In The Presence Of Weights
by: Włodarczyk, Michał
Published: (2024)

Visualizing Treewidth
by: Chiu, Alvin, et al.
Published: (2025)

Dynamic Treewidth in Logarithmic Time
by: Korhonen, Tuukka
Published: (2025)

Spanning and Metric Tree Covers Parameterized by Treewidth
by: Elkin, Michael, et al.
Published: (2025)

E-Graphs as Circuits, and Optimal Extraction via Treewidth
by: Sun, Glenn, et al.
Published: (2024)

Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model
by: Jauregui, Benjamin, et al.
Published: (2018)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
by: Wlodarczyk, Michal
Published: (2023)

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

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

Enumeration of Minimal Hitting Sets Parameterized by Treewidth
by: Kenig, Batya, et al.
Published: (2024)

Treewidth of the $n \times n$ toroidal grid
by: Gima, Tatsuya, et al.
Published: (2026)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Residue Domination in Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2024)

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

Deterministic Single Exponential Time Algorithms for Co-Path Packing and Co-Path Set Parameterized by Treewidth
by: Liu, Yuxi, et al.
Published: (2026)

Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors
by: Sharma, Roohani, et al.
Published: (2026)

Sparse Outerstring Graphs Have Logarithmic Treewidth
by: An, Shinwoo, et al.
Published: (2024)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)

Generalized Graph Packing Problems Parameterized by Treewidth
by: Esmer, Barış Can, et al.
Published: (2025)

Bilateral Treewidth for QBF: Where Strategies and Resolution Meet
by: Ganian, Robert, et al.
Published: (2026)

Snakes and Ladders: a Treewidth Story
by: Chaplick, Steven, et al.
Published: (2023)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

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

Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams
by: Cheng, Bin, et al.
Published: (2025)

FPT Approximation for Capacitated Sum of Radii
by: Jaiswal, Ragesh, et al.
Published: (2024)

Approximation Algorithms for Digraph Width Parameters
by: Kintali, Shiva, et al.
Published: (2011)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

Scalable Fair Influence Blocking Maximization via Approximately Monotonic Submodular Optimization
by: Fang, Qiangpeng, et al.
Published: (2026)

Differentially Private High-Dimensional Approximate Range Counting, Revisited
by: Aumüller, Martin, et al.
Published: (2024)

A Better-Than-1.6-Approximation for Prize-Collecting TSP
by: Blauth, Jannis, et al.
Published: (2023)

3/2-Approximation for the Forest Augmentation Problem
by: Çivril, Ali
Published: (2024)

2-Approximation for Prize-Collecting Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2023)

Approximating Traveling Salesman Problems Using a Bridge Lemma
by: Böhm, Martin, et al.
Published: (2024)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
by: Cabello, Sergio, et al.
Published: (2025)

Approximate Distance Sensitivity Oracles in Subquadratic Space
by: Bilò, Davide, et al.
Published: (2023)