Buchumschlag

Reductions in local certification

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Esperet, Louis, Zeitoun, Sébastien
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Renaming in distributed certification
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2024)

Complexity landscape for local certification
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2025)

A subquadratic certification scheme for P5-free graphs
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2024)

Local certification of forbidden subgraphs
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2024)

Scheduled Jacobian Chaining
von: Märtens, Simon, et al.
Veröffentlicht: (2025)

Fast algorithms for Vizing's theorem on bounded degree graphs
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2023)

Global certification via perfect hashing
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2024)

Local certification of geometric graph classes
von: Defrain, Oscar, et al.
Veröffentlicht: (2023)

Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation
von: Chang, Yen-Hsiang, et al.
Veröffentlicht: (2025)

Local Ratio based Real-time Job Offloading and Resource Allocation in Mobile Edge Computing
von: Gao, Chuanchao, et al.
Veröffentlicht: (2025)

Computing in Anonymous Dynamic Networks Is Linear
von: Di Luna, Giuseppe A., et al.
Veröffentlicht: (2022)

Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
von: Fuchs, Marc, et al.
Veröffentlicht: (2024)

Efficient Parallel $(Δ+1)$-Edge-Coloring
von: Elkin, Michael, et al.
Veröffentlicht: (2026)

A Randomised Approach to Distributed Sorting
von: Olesker-Taylor, Sam
Veröffentlicht: (2025)

Model-Agnostic Approximation of Constrained Forest Problems
von: Coupette, Corinna, et al.
Veröffentlicht: (2024)

GenTT: Generate Vectorized Codes for General Tensor Permutation
von: Chen, Yaojian, et al.
Veröffentlicht: (2025)

Optimal local certification on graphs of bounded pathwidth
von: Baterisna, Dan Alden, et al.
Veröffentlicht: (2025)

Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
von: Izumi, Taisuke, et al.
Veröffentlicht: (2025)

Invitation to Local Algorithms
von: Rozhoň, Václav
Veröffentlicht: (2024)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
von: Izumi, Taisuke, et al.
Veröffentlicht: (2023)

A Cut-Matching Game for Constant-Hop Expanders
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2022)

Lower bound for constant-size local certification
von: Martínez, Virgina Ardévol, et al.
Veröffentlicht: (2022)

Distance-based certification for leader election in meshed graphs and local recognition of their subclasses
von: Chalopin, Jérémie, et al.
Veröffentlicht: (2026)

Moser-Tardos Algorithm with small number of random bits
von: Csóka, Endre, et al.
Veröffentlicht: (2022)

A Tight Meta-theorem for LOCAL Certification of MSO$_2$ Properties within Bounded Treewidth Graphs
von: Cook, Linda, et al.
Veröffentlicht: (2025)

Distributed Reductions for the Maximum Weight Independent Set Problem
von: Borowitz, Jannick, et al.
Veröffentlicht: (2025)

Breaking Barriers for Distributed MIS by Faster Degree Reduction
von: Khoury, Seri, et al.
Veröffentlicht: (2025)

Binsparse: A Specification for Cross-Platform Storage of Sparse Matrices and Tensors
von: Brock, Benjamin, et al.
Veröffentlicht: (2025)

Faster Distributed $Δ$-Coloring via a Reduction to MIS
von: Bourreau, Yann, et al.
Veröffentlicht: (2025)

Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
von: Khoury, Seri, et al.
Veröffentlicht: (2025)

Reducing Matroid Optimization to Basis Search
von: Streit, Robert, et al.
Veröffentlicht: (2024)

Efficient Dynamic MaxFlow Computation on GPUs
von: Kannappan, Shruthi, et al.
Veröffentlicht: (2025)

Towards Optimal Distributed Edge Coloring with Fewer Colors
von: Jakob, Manuel, et al.
Veröffentlicht: (2025)

Perfect Matching with Few Link Activations
von: Mirault, Hugo, et al.
Veröffentlicht: (2025)

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling
von: Feist, Dankrad, et al.
Veröffentlicht: (2025)

Designing Parallel Algorithms for Community Detection using Arachne
von: Li, Fuhuan, et al.
Veröffentlicht: (2025)

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
von: Gil, Yuval, et al.
Veröffentlicht: (2025)

WarpSpeed: A High-Performance Library for Concurrent GPU Hash Tables
von: McCoy, Hunter, et al.
Veröffentlicht: (2025)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
von: Baumecker, Malte, et al.
Veröffentlicht: (2025)