Cover Image

Distributed Treewidth Computation and Courcelle's Theorem in the CONGEST Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jauregui, Benjamin, Li, Jason, Montealegre, Pedro, Todinca, Ioan
Format:	Preprint
Published:	2018
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Distributed Model Checking on Graphs of Bounded Treedepth
by: Fomin, Fedor V., et al.
Published: (2024)

Deterministic Even-Cycle Detection in Broadcast CONGEST
by: Fraigniaud, Pierre, et al.
Published: (2024)

Courcelle's Theorem for Lipschitz Continuity
by: Gima, Tatsuya, et al.
Published: (2025)

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
by: Blin, Lélia, et al.
Published: (2024)

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

Tight Lieb-Robinson Bound for approximation ratio in Quantum Annealing
by: Braida, Arthur, et al.
Published: (2023)

Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing
by: Braida, Arthur, et al.
Published: (2023)

Polynomial kernels for edge modification problems towards block and strictly chordal graphs
by: Dumas, Maël, et al.
Published: (2022)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

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

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

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

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

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

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

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

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

Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks
by: Gall, François Le, et al.
Published: (2018)

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

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

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
by: Manoharan, Vignesh, et al.
Published: (2023)

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)

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

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

Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
by: Manoharan, Vignesh, et al.
Published: (2022)

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

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

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

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

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)

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

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

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

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)

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)