Some recognition problems related to graph isomorphism

DOI10.1007/BF01082603MaRDI QIDQ3470503zbMATH OpenFDO

Authors Vadim G. Timkovsky

Publication date 1988

Published in Cybernetics (Search for Journal in Brave)

zbMATH Keywords

computational complexitymathematical programminggraph isomorphismNP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• A heuristic algorithm of recognition of isomorphism of graphs
• scientific article; zbMATH DE number 3841910
• Graph isomorphism problem
• scientific article; zbMATH DE number 3815
• On recognizing graphs by numbers of homomorphisms
• Recent advances on the graph isomorphism problem
• Graph algebras and the graph isomorphism problem
• On the recognition complexity of some graph properties
• Publication:4206773

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3333883 (Why is no real title available?)
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On the Set-Covering Problem
• Subcomplete generalizations of graph isomorphism
• THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS

Cited in

(15)

• Graph isomorphism problem in terms of probability propagation matrix invariance criterion by using ITCPP
• The graph isomorphism problem on geometric graphs
• Functional approach to the Hamiltonian circuit and graph isomorphism problems
• scientific article; zbMATH DE number 4053667 (Why is no real title available?)
• scientific article; zbMATH DE number 3841910 (Why is no real title available?)
• Star partitions and the graph isomorphism problem
• A general comparative study of some aspects of graph isomorphism
• scientific article; zbMATH DE number 4041268 (Why is no real title available?)
• Minimization procedure for Hamiltonian circuit and graph isomorphism problems
• Neighborhood hypergraphs of bipartite graphs
• Isomorphism identification of graphs: especially for the graphs of kinematic chains
• Graph approach to solving problems of combinatorial recognition
• Polynomial equivalence of the problems ``predicate formulas isomorphism and graph isomorphism
• scientific article; zbMATH DE number 7145105 (Why is no real title available?)
• Isomorphism for digraphs and sequences of shop scheduling problems

This page was built for publication: Some recognition problems related to graph isomorphism

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