Colored hypergraph isomorphism is fixed parameter tractable

DOI10.4230/LIPICS.FSTTCS.2010.327MaRDI QIDQ2908862zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexityfixed parameter tractabilityfpt algorithmsgraph isomorphism

Mathematics Subject Classification ID

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

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

Cited in

(7)

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

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)