Distributed model checking on graphs of bounded treedepth
From MaRDI portal
Cites work
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- A hierarchy of local decision
- A meta-theorem for distributed certification
- A partial k-arboretum of graphs with bounded treewidth
- Algorithmic meta-theorems
- Almost-Tight Distributed Minimum Cut Algorithms
- Approximate proof-labeling schemes
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Compact distributed certification of planar graphs
- Distributed approximation algorithms for weighted shortest paths
- Distributed Computing: A Locality-Sensitive Approach
- Distributed connectivity decomposition
- Distributed minimum cut approximation
- Distributed quantum interactive proofs
- Distributed verification and hardness of distributed approximation
- Distributed zero-knowledge proofs over networks
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Fast and compact self-stabilizing verification, computation, and fault detection of an MST
- Fast distributed construction of k-dominating sets and applications
- Graph minors. III. Planar tree-width
- Improved distributed Steiner forest construction
- Interactive distributed proofs
- Introduction to local certification
- Kernelizing MSO properties of trees of fixed height, and some consequences
- Local Certification of Graph Decompositions and Applications to Minor-Free Classes
- Local certification of graphs on surfaces
- Local certification of graphs with bounded genus
- Locally checkable proofs in distributed computing
- Logic, graphs, and algorithms
- Low-congestion shortcuts without embedding
- Methods for algorithmic meta theorems
- Near-optimal distributed DFS in planar graphs
- Near-optimal distributed maximum flow (extended abstract)
- On the power of the congested clique model
- Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms
- Planarity can be verified by an approximate proof labeling scheme in constant-time
- Proof labeling schemes
- Randomized distributed decision
- Randomized proof-labeling schemes
- Redundancy in distributed proofs
- Sparsity. Graphs, structures, and algorithms
- Survey of distributed decision
- Testability and local certification of monotone properties in minor-closed classes
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The power of distributed verifiers in interactive proofs
- Towards a complexity theory for local distributed computing
- Trade-offs in distributed interactive proofs
- What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
- What can be decided locally without identifiers?
- What can be verified locally?
- Where first-order and monadic second-order logic coincide
This page was built for publication: Distributed model checking on graphs of bounded treedepth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6883632)
