Colored hypergraph isomorphism is fixed parameter tractable

DOI10.4230/LIPICS.FSTTCS.2010.327zbMATH Open1245.68098OpenAlexW2171133573MaRDI QIDQ2908862FDOQ2908862

Authors: Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda 

Publication date: 29 August 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_394c.html

Recommendations

• Colored hypergraph isomorphism is fixed parameter tractable
• On Hypergraph and Graph Isomorphism with Bounded Color Classes
• Parameterized complexity of small weight automorphisms
• Parameterized complexity of small weight automorphisms and isomorphisms
• On tractable parameterizations of graph isomorphism

zbMATH Keywords

computational complexitygraph isomorphismfixed parameter tractabilityfpt algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cited In (7)

• On weak isomorphism of rooted vertex-colored graphs
• Colored hypergraph isomorphism is fixed parameter tractable
• Hypergraph Isomorphism for Groups with Restricted Composition Factors
• Parameterized complexity of small weight automorphisms
• Parameterized complexity of small weight automorphisms and isomorphisms
• Towards an isomorphism dichotomy for hereditary graph classes
• On Hypergraph and Graph Isomorphism with Bounded Color Classes

This page was built for publication: Colored hypergraph isomorphism is fixed parameter tractable

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