Copertina

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Blin, Lélia, Fomin, Fedor V., Fraigniaud, Pierre, Gay, Sylvain, Golovach, Petr A., Montealegre, Pedro, Rapaport, Ivan, Todinca, Ioan
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms F.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

Informative Trains: A Memory-Efficient Journey to a Self-Stabilizing Leader Election Algorithm in Anonymous Graphs
di: Blin, Lelia, et al.
Pubblicazione: (2026)

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

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

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

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

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

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

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

Fault-Tolerant Matroid Bases
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

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

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

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

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

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

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

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

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

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

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

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

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

Discounted Cuts: A Stackelberg Approach to Network Disruption
di: Drange, Pål Grønås, et al.
Pubblicazione: (2025)

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

Even-Cycle Detection in the Randomized and Quantum CONGEST Model
di: Fraigniaud, Pierre, et al.
Pubblicazione: (2024)

Packing Short Cycles
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

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

Source-Oblivious Broadcast
di: Fraigniaud, Pierre, et al.
Pubblicazione: (2025)

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

Line Cover and Related Problems
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
di: Golovach, Petr A., et al.
Pubblicazione: (2022)

Polynomial Kernels for Spanning Tree with Diversity Requirements
di: Golovach, Petr A., et al.
Pubblicazione: (2026)

Revisiting Local Computation of PageRank: Simple and Optimal
di: Wang, Hanzhi, et al.
Pubblicazione: (2024)

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

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

The Topology of Local Computing in Networks
di: Fraigniaud, Pierre, et al.
Pubblicazione: (2020)

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

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