Colored hypergraph isomorphism is fixed parameter tractable
From MaRDI portal
Publication:2258076
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/
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