Cover Image

A Faster Isomorphism Test for Graphs of Small Degree

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Grohe, Martin, Neuen, Daniel, Schweitzer, Pascal
Format:	Preprint
Published:	2018
Subjects:	Data Structures and Algorithms Discrete Mathematics Combinatorics Group Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

Explicit Lossless Vertex Expanders
by: Hsieh, Jun-Ting, et al.
Published: (2025)

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

The Iteration Number of the Weisfeiler-Leman Algorithm
by: Grohe, Martin, et al.
Published: (2023)

The $Z$-Curve as an $n$-Dimensional Hypersphere: Properties and Analysis
by: Gonzalez, Diego Vazquez, et al.
Published: (2024)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
by: Iwata, Satoru, et al.
Published: (2024)

Sandwich Monotonicity and the Recognition of Weighted Graph Classes
by: Beisegel, Jesse, et al.
Published: (2025)

Colouring Probe $H$-Free Graphs
by: Paulusma, Daniël, et al.
Published: (2025)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Tree Independence Number IV. Even-hole-free Graphs
by: Chudnovsky, Maria, et al.
Published: (2024)

EPTAS for Hard Graph Cut Problems for Dense Graphs
by: Deguchi, Kaisei, et al.
Published: (2026)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
by: Charbit, Pierre, et al.
Published: (2025)

Computational Verification of the Buratti--Horak--Rosa Conjecture for Small Integers and Inductive Approaches
by: Naik, Ranjan N
Published: (2025)

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

$α_i$-Metric Graphs: Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

Construction of orientable sequences in $O(1)$-amortized time per bit
by: Gabric, Daniel, et al.
Published: (2024)

Hardness of Burning Number Problem on Regular Graphs
by: Antony, Dhanyamol, et al.
Published: (2026)

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

Graph parameters that are coarsely equivalent to path-length
by: Dragan, Feodor F., et al.
Published: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

The Complexity of Temporal Vertex Cover in Small-Degree Graphs
by: Hamm, Thekla, et al.
Published: (2022)

On constrained intersection representations of graphs and digraphs
by: Cicalese, Ferdinando, et al.
Published: (2025)

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
by: Holtgrefe, Niels, et al.
Published: (2024)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

A Uniformly Random Solution to Algorithmic Redistricting
by: Cai, Jin-Yi, et al.
Published: (2024)

A Method for Generating Connected Erdos-Renyi Random Graphs
by: Chinyaev, Boris
Published: (2025)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Holey graphs: very large Betti numbers are testable
by: Szabó, Dániel, et al.
Published: (2024)

Unsplittable Transshipments
by: Debgupta, Srinwanti, et al.
Published: (2026)