Cover Image

The Iteration Number of the Weisfeiler-Leman Algorithm

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Grohe, Martin, Lichter, Moritz, Neuen, Daniel
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Discrete Mathematics Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
by: Grohe, Martin, et al.
Published: (2023)

Isomorphism for Tournaments of Small Twin Width
by: Grohe, Martin, et al.
Published: (2023)

Weisfeiler-Leman on graphs of small twin-width
by: Heinrich, Irene, et al.
Published: (2026)

Beyond Value Iteration for Parity Games: Strategy Iteration with Universal Trees
by: Koh, Zhuan Khye, et al.
Published: (2021)

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
by: Dahan, Anatole, et al.
Published: (2026)

Bounding the Weisfeiler-Leman Dimension via a Depth Analysis of I/R-Trees
by: Kiefer, Sandra, et al.
Published: (2024)

Formal Primal-Dual Algorithm Analysis
by: Abdulaziz, Mohammad, et al.
Published: (2026)

A Faster Isomorphism Test for Graphs of Small Degree
by: Grohe, Martin, et al.
Published: (2018)

Solving Partial Dominating Set and Related Problems Using Twin-Width
by: Balabán, Jakub, et al.
Published: (2025)

Foundations for an Abstract Proof Theory in the Context of Horn Rules
by: Lyon, Tim S., et al.
Published: (2023)

On Numbers of Simplicial Walks and Equivalent Canonizations for Graph Recognition
by: Černý, Marek
Published: (2026)

Color Refinement for Relational Structures
by: Scheidt, Benjamin, et al.
Published: (2024)

On classes of bounded tree rank, their interpretations, and efficient sparsification
by: Gajarský, Jakub, et al.
Published: (2024)

SDPs and Robust Satisfiability of Promise CSP
by: Brakensiek, Joshua, et al.
Published: (2022)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
by: Majewski, Konrad, et al.
Published: (2021)

Flipper games for monadically stable graph classes
by: Gajarský, Jakub, et al.
Published: (2023)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

On merge-models
by: Buffière, Hector, et al.
Published: (2026)

CNFs and DNFs with Exactly $k$ Solutions
by: Chandran, L. Sunil, et al.
Published: (2025)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

Isomorphism Testing Parameterized by Genus and Beyond
by: Neuen, Daniel
Published: (2021)

Merge-width and First-Order Model Checking
by: Dreier, Jan, et al.
Published: (2025)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
by: Barto, Libor, et al.
Published: (2024)

SAT Encoding of Partial Ordering Models for Graph Coloring Problems
by: Faber, Daniel, et al.
Published: (2024)

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing
by: Černý, Marek, et al.
Published: (2025)

Smaller Circuits for Bit Addition
by: Goncharov, Mikhail, et al.
Published: (2025)

The Weisfeiler-Leman Dimension of Conjunctive Queries
by: Göbel, Andreas, et al.
Published: (2023)

An Upper Bound on the Weisfeiler-Leman Dimension
by: Schneider, Thomas, et al.
Published: (2024)

Redundancy Is All You Need (for CSP Sparsification)
by: Brakensiek, Joshua, et al.
Published: (2024)

Computational complexity of the Weisfeiler-Leman dimension
by: Lichter, Moritz, et al.
Published: (2024)

The Complexity of Homomorphism Reconstruction Revisited
by: Gervens, Timo, et al.
Published: (2026)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Treewidth Parameterized by Feedback Vertex Number
by: Molter, Hendrik, et al.
Published: (2025)

On the Number of Non-equivalent Parameterized Squares in a String
by: Hamai, Rikuya, et al.
Published: (2024)

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

Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
by: Zhang, Bohang, et al.
Published: (2024)

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

Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
by: Kaul, Matthias, et al.
Published: (2024)