Computational complexity of computing a partial solution for the graph automorphism problems

DOI10.1016/j.tcs.2009.01.001zbMath1168.68020OpenAlexW2057674369MaRDI QIDQ1019184

Takayuki Nagoya, Seinosuke Toda

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.01.001

zbMATH Keywords

computational complexityreducibilitygraph automorphismpartial solution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Polynomial time algorithms for variants of graph matching on partial \(k\)-trees

Cites Work

• Unnamed Item
• A note on decision versus search for graph automorphism
• A note on the graph isomorphism counting problem
• Computing complete graph isomorphisms and Hamiltonian cycles from partial ones
• Computing graph automorphism from partial solutions
• Graph Isomorphism is in SPP
• Some NP-Complete Problems Similar to Graph Isomorphism
• The graph isomorphism disease
• On the Hardness of Graph Isomorphism

This page was built for publication: Computational complexity of computing a partial solution for the graph automorphism problems