Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
type: Item
instance of: scholarly article
zbMATH Open document ID: 1443.68118
author: Vikraman Arvind
author: Sebastian Kuhnert
author: Johannes Köbler
author: Jacobo Torán
publication date: 2020-05-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/1709.10063
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 68Q27
zbMATH DE Number: 7205186
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: hypergraph isomorphism
zbMATH Keywords: mislabeled graphs
MaRDI profile type: MaRDI publication profile
arXiv classification: cs.CC
arXiv classification: math.CO
arXiv ID: 1709.10063
cites work: Parameterized Complexity of Small Weight Automorphisms.
cites work: Graph isomorphism in quasipolynomial time [extended abstract]
cites work: Q4882944
cites work: Q4503944
cites work: Storing a Sparse Table with 0 (1) Worst Case Access Time
cites work: Q3912839
cites work: Completeness results for graph isomorphism.
cites work: Graph isomorphism restricted by lists
cites work: Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
cites work: Some NP-Complete Problems Similar to Graph Isomorphism
cites work: Isomorphism of (mis)Labeled Graphs
OpenAlex ID: W2964045964
title: Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
DOI: 10.4230/LIPICS.IPEC.2017.2
Recommended article: Parameterized complexity of small weight automorphisms and isomorphisms
Recommended article: Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor
Recommended article: On Tractable Parameterizations of Graph Isomorphism
Recommended article: Parameterized Complexity of Small Weight Automorphisms.
Recommended article: Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
Recommended article: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Recommended article: Parameterized complexity of finding small degree-constrained subgraphs
Recommended article: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
Recommended article: Restricted space algorithms for isomorphism on bounded treewidth graphs
Recommended article: A convex relaxation bound for subgraph isomorphism
description: scientific article; zbMATH DE number 7205186