Some NP-Complete Problems Similar to Graph Isomorphism
From MaRDI portal
Publication:3902476
DOI10.1137/0210002zbMath0454.68025OpenAlexW2041176939WikidataQ55894627 ScholiaQ55894627MaRDI QIDQ3902476
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
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
