Cover Image

Distributed Model Checking on Graphs of Bounded Treedepth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fomin, Fedor V., Fraigniaud, Pierre, Montealegre, Pedro, Rapaport, Ivan, Todinca, Ioan
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

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

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

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

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

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

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

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

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

Computing Treedepth Obstructions
by: Kühn, Kolja
Published: (2025)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
by: Bodlaender, Hans L., et al.
Published: (2025)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

Source-Oblivious Broadcast
by: Fraigniaud, Pierre, et al.
Published: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)

Algorithmic Extensions of Dirac's Theorem
by: Fomin, Fedor V., et al.
Published: (2020)

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

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

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

When does FTP become FPT?
by: Bentert, Matthias, et al.
Published: (2025)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

H-Planarity and Parametric Extensions: when Modulators Act Globally
by: Fomin, Fedor V., et al.
Published: (2025)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

Packing Short Cycles
by: Bentert, Matthias, et al.
Published: (2024)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
by: Bai, Tian, et al.
Published: (2026)

FO and MSO Model Checking on Temporal Graphs
by: Döring, Michelle, et al.
Published: (2026)

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
by: Dudek, Bartłomiej, et al.
Published: (2026)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
by: Fomin, Fedor V., et al.
Published: (2024)

Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
by: Hu, Ivan, et al.
Published: (2022)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
by: Fomin, Fedor V., et al.
Published: (2026)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
by: Feldmann, Andreas Emil, et al.
Published: (2024)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)