Cover Image

A subquadratic certification scheme for P5-free graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bousquet, Nicolas, Zeitoun, Sébastien
Format:	Preprint
Published:	2024
Subjects:	Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Complexity landscape for local certification
by: Bousquet, Nicolas, et al.
Published: (2025)

Renaming in distributed certification
by: Bousquet, Nicolas, et al.
Published: (2024)

Local certification of forbidden subgraphs
by: Bousquet, Nicolas, et al.
Published: (2024)

Reductions in local certification
by: Esperet, Louis, et al.
Published: (2025)

Global certification via perfect hashing
by: Bousquet, Nicolas, et al.
Published: (2024)

Fast algorithms for Vizing's theorem on bounded degree graphs
by: Bernshteyn, Anton, et al.
Published: (2023)

Simpler and More General Distributed Coloring Based on Simple List Defective Coloring Algorithms
by: Fuchs, Marc, et al.
Published: (2024)

Parallelizing the Approximate Minimum Degree Ordering Algorithm: Strategies and Evaluation
by: Chang, Yen-Hsiang, et al.
Published: (2025)

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

Computing in Anonymous Dynamic Networks Is Linear
by: Di Luna, Giuseppe A., et al.
Published: (2022)

Efficient Parallel $(Δ+1)$-Edge-Coloring
by: Elkin, Michael, et al.
Published: (2026)

A Randomised Approach to Distributed Sorting
by: Olesker-Taylor, Sam
Published: (2025)

Scheduled Jacobian Chaining
by: Märtens, Simon, et al.
Published: (2025)

Model-Agnostic Approximation of Constrained Forest Problems
by: Coupette, Corinna, et al.
Published: (2024)

GenTT: Generate Vectorized Codes for General Tensor Permutation
by: Chen, Yaojian, et al.
Published: (2025)

Optimal local certification on graphs of bounded pathwidth
by: Baterisna, Dan Alden, et al.
Published: (2025)

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

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

Lower bound for constant-size local certification
by: Martínez, Virgina Ardévol, et al.
Published: (2022)

Independent set reconfiguration in H-free graphs
by: Bartier, Valentin, et al.
Published: (2024)

Binsparse: A Specification for Cross-Platform Storage of Sparse Matrices and Tensors
by: Brock, Benjamin, et al.
Published: (2025)

The Blocklace: A Byzantine-repelling and Universal Conflict-free Replicated Data Type
by: Almeida, Paulo Sérgio, et al.
Published: (2024)

Local certification of geometric graph classes
by: Defrain, Oscar, et al.
Published: (2023)

The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
by: Lechowicz, Adam, et al.
Published: (2023)

Reducing Matroid Optimization to Basis Search
by: Streit, Robert, et al.
Published: (2024)

A Simple and Robust Protocol for Distributed Counting
by: Cohen, Edith, et al.
Published: (2025)

A Simple Distributed Deterministic Planar Separator
by: Abd-Elhaleem, Yaseen, et al.
Published: (2026)

A Hybrid Vectorized Merge Sort on ARM NEON
by: Zhou, Jincheng, et al.
Published: (2024)

A Scalable and Unified Framework to Weighted Rank Aggregation
by: Carmel, Amir, et al.
Published: (2026)

A Parallel Scan Algorithm in the Tensor Core Unit Model
by: Zouzias, Anastasios, et al.
Published: (2024)

A Distributed Conductance Tester Without Global Information Collection
by: Batu, Tugkan, et al.
Published: (2023)

A Fault-Tolerant Version of Safra's Termination Detection Algorithm
by: Fokkink, Wan, et al.
Published: (2026)

A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems
by: Li, Qian, et al.
Published: (2024)

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
by: Gil, Yuval, et al.
Published: (2025)

A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
by: Cambus, Mélanie, et al.
Published: (2022)

Can Like Attract Like? A Study of Homonymous Gathering in Networks
by: Devismes, Stéphane, et al.
Published: (2025)

Engineering A Workload-balanced Push-Relabel Algorithm for Massive Graphs on GPUs
by: Hsieh, Chou-Ying, et al.
Published: (2024)

Skip Hash: A Fast Ordered Map Via Software Transactional Memory
by: Rodriguez, Matthew, et al.
Published: (2024)

BinomialHash: A Constant Time, Minimal Memory Consistent Hash Algorithm
by: Coluzzi, Massimo, et al.
Published: (2024)

WarpSpeed: A High-Performance Library for Concurrent GPU Hash Tables
by: McCoy, Hunter, et al.
Published: (2025)