Some NP-Complete Problems Similar to Graph Isomorphism

DOI10.1137/0210002zbMath0454.68025OpenAlexW2041176939WikidataQ55894627 ScholiaQ55894627MaRDI QIDQ3902476

Anna Lubiw

Publication date: 1981

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0210002

zbMATH Keywords

graph automorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (34)

Characterizing and computing weight-equitable partitions of graphs ⋮ The complexity of Boolean matrix root computation ⋮ Realizability and uniqueness in graphs ⋮ On the complexity of reconstructing H-free graphs from their Star Systems ⋮ On rotational symmetries of drawings of coherent periodic graphs ⋮ Reconstructing a Graph from its Neighborhood Lists ⋮ Polynomial time algorithms for variants of graph matching on partial \(k\)-trees ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ A correction to Colbourn's paper on the complexity of matrix symmetrizability ⋮ Le problème d'étoiles pour graphes est NP-complèt ⋮ Symmetry detection and classification in drawings of graphs ⋮ Geometric automorphism groups of graphs ⋮ Applications of dimensionality reduction and exponential sums to graph automorphism ⋮ Circulant graphs: recognizing and isomorphism testing in polynomial time ⋮ Computing graph automorphism from partial solutions ⋮ Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ Exploring Symmetries to Decompose Matrices and Graphs Preserving the Spectrum ⋮ A linear-time algorithm for symmetric convex drawings of internally triconnected plane graphs ⋮ Graph isomorphism restricted by lists ⋮ On the Complexity of Reconstructing H-free Graphs from Their Star Systems ⋮ On the subgroup distance problem. ⋮ Computational complexity of computing a partial solution for the graph automorphism problems ⋮ Linear optimization over permutation groups ⋮ Algorithms for the fixed point property ⋮ Subcomplete generalizations of graph isomorphism ⋮ Drawing series parallel digraphs symmetrically ⋮ On the isomorphism of expressions ⋮ Graph isomorphism problem ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ Circulant graphs: efficient recognizing and isomorphism testing ⋮ Quadratic forms and the graph isomorphism problem ⋮ Finding fixed point free elements and small bases in permutation groups

This page was built for publication: Some NP-Complete Problems Similar to Graph Isomorphism