Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable

DOI10.4230/LIPIcs.IPEC.2017.2zbMath1443.68118arXiv1709.10063OpenAlexW2964045964MaRDI QIDQ5111861

Sebastian Kuhnert, V. Arvind, Johannes Köbler, Jacobo Toran

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1709.10063

zbMATH Keywords

parameterized algorithmshypergraph isomorphismmislabeled graphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Parameterized complexity of small weight automorphisms and isomorphisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness results for graph isomorphism.
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Isomorphism of (mis)Labeled Graphs
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Some NP-Complete Problems Similar to Graph Isomorphism
• Parameterized Complexity of Small Weight Automorphisms.
• Graph isomorphism in quasipolynomial time [extended abstract]
• Graph isomorphism restricted by lists

This page was built for publication: Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable