Cover Image

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Levet, Michael, Rombach, Puck, Sieger, Nicholas
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Computational Complexity Logic in Computer Science Combinatorics 05C60, 68Q19, 68Q25, 68R10 F.2.2; G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
by: Oliveria, Mateus de Oliveira, et al.
Published: (2026)

Interval Graphs are Reconstructible
by: Heinrich, Irene, et al.
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

On the twin-width of near-regular graphs
by: Heinrich, Irene, et al.
Published: (2025)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
by: Jain, Rahul, et al.
Published: (2019)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

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

State Canonization and Early Pruning in Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

Symbolic Model Checking in External Memory
by: Sølvsten, Steffan Christ, et al.
Published: (2025)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
by: Demaine, Erik D., et al.
Published: (2024)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
by: Liao, Chao, et al.
Published: (2022)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Optimal non-adaptive algorithm for edge estimation
by: Bishnu, Arijit, et al.
Published: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Pliability and Approximating Max-CSPs
by: Romero, Miguel, et al.
Published: (2019)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

Experimental algorithms for the dualization problem
by: Mezzini, Mauro, et al.
Published: (2025)

DAG Scheduling in the BSP Model
by: Papp, Pál András, et al.
Published: (2023)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

Maximum Matchings in Geometric Intersection Graphs
by: Bonnet, Édouard, et al.
Published: (2019)

O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
by: Bell, Tolson, et al.
Published: (2024)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

Large cliques and large independent sets: can they coexist?
by: Feige, Uriel, et al.
Published: (2025)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)