Some NP-Complete Problems Similar to Graph Isomorphism

DOI10.1137/0210002MaRDI QIDQ3902476zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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)

Cited in

(35)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3902476)