The parameterized complexity of fixing number and vertex individualization in graphs

DOI10.1145/3558077MaRDI QIDQ7023435zbMATH OpenFDO

Authors Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, Gaurav Rattan

Publication date 21 February 2025

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3558077

zbMATH Keywords

base sizefixing numbergraph automorphismgraph isomorphismindividualizationpermutation groupsWeisfeiler-Leman procedure

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

This page was built for publication: The parameterized complexity of fixing number and vertex individualization in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023435)