Colored hypergraph isomorphism is fixed parameter tractable

DOI10.1007/s00453-013-9787-yzbMath1308.68061OpenAlexW2084458866MaRDI QIDQ2258076

Johannes Köbler, Bireswar Das, V. Arvind

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2875/

zbMATH Keywords

computational complexityfixed parameter tractabilitygraph isomorphismfpt algorithms

Mathematics Subject Classification ID

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

Related Items (5)

Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ Order Reconfiguration under Width Constraints ⋮ Automorphisms of the cube \(n^d\) ⋮ VF2++ -- an improved subgraph isomorphism algorithm ⋮ Automorphisms of the Cube $$n^d$$

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Isomorphism for graphs of bounded distance width
• Completeness results for graph isomorphism.
• Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks
• Parametrized complexity theory.
• Hypergraph isomorphism and structural equivalence of Boolean functions
• COLORED HYPERGRAPH ISOMORPHISM is fixed parameter tractable
• Canonizing Hypergraphs under Abelian Group Action
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• Fixed-Parameter Tractability and Completeness I: Basic Results
• On Hypergraph and Graph Isomorphism with Bounded Color Classes
• Logical Approaches to Computational Barriers

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