About: Graph isomorphism problem

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Computational problem of determining whether two finite graphs are isomorphic

Property	Value
dbo:description	problema computazionale (it) בעיה חישובית (iw) computational problem of determining whether two finite graphs are isomorphic (en) рачунарски проблем (sr) مسئله‌ی رایانشی (fa)
dbo:thumbnail	wiki-commons:Special:FilePath/Graph_isomorphisms.svg?width=300
dbo:wikiPageExternalLink	http://eprintweb.org/S/authors/All/ka/Kaibel/16 http://theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column97.pdf https://web.archive.org/web/20100920154742/http:/theorie.informatik.uni-ulm.de/Personen/toran/beatcs/column97.pdf https://web.archive.org/web/20150721175904/http:/eprintweb.org/S/authors/All/ka/Kaibel/16 https://archive.org/details/stacs200017thann0000annu/page/431 https://books.google.com/books%3Fid=bHGy0_H0g8QC&pg=PA120 https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/toran/beatcs/column86.pdf http://cs.anu.edu.au/~bdm/nauty/PGI/ https://www.cs.uchicago.edu/~laci/papers/hypergraphiso.pdf https://escholarship.org/uc/item/8ss2q7bp http://dl.acm.org/citation.cfm%3Fid=800261.809095 http://www.cse.iitm.ac.in/~ravi/papers/Shravan-ICML08.pdf https://hal.inria.fr/inria-00076553/document http://www.cs.sunysb.edu/~algorith http://www.cs.sunysb.edu/~algorith/files/graph-isomorphism.shtml http://www.engr.uconn.edu/~vkk06001/GraphIsomorphism/Papers/VF_SD_NAUTY_Ullman_Experiments.pdf http://www.cs.uwaterloo.ca/research/tr/2006/CS-2006-32.pdf http://www.cs.bgu.ac.il/~dinitz/Course/SS-12/Ullman_Algorithm.pdf
dbo:wikiPageWikiLink	dbr:NC_(complexity) dbr:Oracle_machine dbr:Mathematical_chemistry dbc:Computational_problems_in_graph_theory dbr:Tree_(graph_theory) dbr:Strongly_regular_graph dbr:Classification_of_finite_simple_groups dbc:Unsolved_problems_in_computer_science dbr:NP-intermediate dbr:Circuit_diagram dbc:Graph_algorithms dbr:Chemical_compound dbr:NP_(complexity) dbr:Parity_P dbc:Morphisms dbr:Graph_isomorphism dbr:Computer_vision dbr:Pattern_recognition dbr:Layout_Versus_Schematic dbr:Lecture_Notes_in_Computer_Science dbr:Multigraph dbc:Computational_complexity_theory dbr:Combinatorial_chemistry dbr:Split_graph dbr:Directed_graph dbr:Permutation_group dbr:Pacific_Journal_of_Mathematics dbr:Information_and_Computation dbr:Eulerian_graph dbr:Chordal_graph dbr:Interval_graph dbr:Nilpotent dbr:Clique_problem dbr:Directed_acyclic_graph dbr:Electronic_design_automation dbr:L_(complexity) dbr:Nondeterministic_Turing_machine dbr:Convex_polytope dbr:Graph_canonization dbr:Bipartite_graph dbr:Markov_decision_process dbr:Structure_(mathematical_logic) dbr:Hypergraph dbr:Algebra_over_a_field dbr:Las_Vegas_algorithm dbr:Chemical_database dbr:Complete_(complexity) dbr:Subgraph_isomorphism_problem dbr:Chemical_substance dbr:László_Babai dbr:Equivalence_relation dbr:Information_Processing_Letters dbr:Best,_worst_and_average_case dbr:Eigenvalue dbr:Semigroup dbr:Integrated_circuit_layout dbr:Complete_graph dbr:Context-free_grammar dbr:ZPP_(complexity) dbr:Cheminformatics dbr:Complexity_class dbr:Symmetric_group dbr:Image_recognition dbr:P_(complexity) dbr:Molecular_graph dbr:Journal_of_the_ACM dbr:Self-complementary_graph dbr:Genus_(mathematics) dbr:Data_mining dbr:Abelian_group dbr:Line_graph dbr:Time_complexity dbr:Computational_problem dbr:Treewidth dbr:Harald_Helfgott dbr:Degree_(graph_theory) dbr:Identifier dbr:Connected_graph dbr:Graph_(discrete_mathematics) dbr:Planar_graph dbr:Computers_and_Intractability dbr:Graph_automorphism_problem dbr:Regular_graph dbr:Circulant_graph dbr:Permutation_graph dbr:Simple_polytope dbr:Simplicial_polytope dbr:Symposium_on_Theoretical_Aspects_of_Computer_Science dbr:Radius_(graph_theory) dbr:Low_(complexity) dbr:Commutative dbr:ACM_SIGACT_News dbr:AM_(complexity) dbr:Hidden_subgroup_problem dbr:Journal_of_Computer_and_System_Sciences dbr:Graphs_and_Combinatorics dbr:SIAM_Journal_on_Computing dbr:Automorphism_group dbr:ACM_Transactions_on_Algorithms dbr:Electric_circuit dbr:NP-complete dbr:Polynomial_time dbr:Sub-exponential_time dbr:Graph_matching dbr:Random_graphs dbr:Diameter_(graph_theory) dbr:Finite_automata dbr:Balanced_incomplete_block_design dbr:Leningrad_Department_of_Steklov_Instit...atics_of_the_USSR_Academy_of_Sciences dbr:Empty_graph dbr:H-description dbr:Class_NP dbr:Colored_graph dbr:Combinatorial_isomorphism dbr:Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness dbr:Labelled_graph dbr:Low_hierarchy dbr:Associative dbr:InChI dbr:Information_and_Control dbr:Polynomial-time_Turing_reduction dbr:Polynomial_time_hierarchy dbr:Polytopal_graph dbr:SMILES dbr:V-description
dbp:author1Link	Manuel Blum (en)
dbp:authorlink	László Babai (en)
dbp:first	Manuel (en) Sampath (en) László (en)
dbp:last	Babai (en) Blum (en) Kannan (en)
dbp:wikiPageUsesTemplate	dbt:Authority_control dbt:Reflist dbt:Math dbt:Sqrt dbt:Citation dbt:Use_American_English dbt:Refend dbt:Sfnp dbt:As_of dbt:Refbegin dbt:Harv dbt:Harvs dbt:Harvtxt dbt:Unsolved dbt:Short_description
dbp:year	1980 (xsd:integer) 1995 (xsd:integer)
dct:subject	dbc:Computational_problems_in_graph_theory dbc:Unsolved_problems_in_computer_science dbc:Graph_algorithms dbc:Morphisms dbc:Computational_complexity_theory dbc:Quasi-polynomial_time_algorithms
gold:hypernym	dbr:Problem
rdfs:label	Graph isomorphism problem (en) Graphen-Isomorphismusproblem (de) Problema del isomorfismo de grafos (es) Problème de l'isomorphisme de graphes (fr) Задача изоморфности графов (ru) Problema de isomorfismo de grafos (pt)
owl:sameAs	freebase:Graph isomorphism problem yago-res:Graph isomorphism problem wikidata:Graph isomorphism problem dbpedia-de:Graph isomorphism problem dbpedia-fr:Graph isomorphism problem dbpedia-pt:Graph isomorphism problem dbpedia-es:Graph isomorphism problem dbpedia-fa:Graph isomorphism problem dbpedia-ru:Graph isomorphism problem dbpedia-et:Graph isomorphism problem dbpedia-sr:Graph isomorphism problem dbpedia-global:Graph isomorphism problem
prov:wasDerivedFrom	wikipedia-en:Graph_isomorphism_problem?oldid=1294675928&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Graph_isomorphisms.svg
foaf:isPrimaryTopicOf	wikipedia-en:Graph_isomorphism_problem
is dbo:wikiPageDisambiguates of	dbr:GIP dbr:Isomorphism_problem dbr:GI
is dbo:wikiPageRedirects of	dbr:GI_(complexity) dbr:Exact_graph_matching dbr:GI-complete
is dbo:wikiPageWikiLink of	dbr:Timeline_of_mathematics dbr:Polynomial-time_reduction dbr:Brendan_McKay_(mathematician) dbr:Eugene_M._Luks dbr:NP-completeness dbr:P_versus_NP_problem dbr:Graph_property dbr:NP-intermediate dbr:Parity_P dbr:GIP dbr:Graph_isomorphism dbr:Uwe_Schöning dbr:Zero-knowledge_proof dbr:Isomorphism_problem dbr:List_of_unsolved_problems_in_computer_science dbr:Convex_polytope dbr:Cadabra_(computer_program) dbr:Graph_canonization dbr:Graph_theory dbr:Andrew_M._Gleason dbr:Fulkerson_Prize dbr:Las_Vegas_algorithm dbr:Subgraph_isomorphism_problem dbr:Lexicographic_product_of_graphs dbr:László_Babai dbr:Manuel_Blum dbr:Computational_complexity_theory dbr:GI dbr:Interactive_proof_system dbr:GI_(complexity) dbr:Self-complementary_graph dbr:Time_complexity dbr:Harald_Helfgott dbr:IP_(complexity) dbr:List_of_University_of_Oregon_faculty_and_staff dbr:Planar_graph dbr:Computers_and_Intractability dbr:Graph_automorphism dbr:Low_(complexity) dbr:Fractional_graph_isomorphism dbr:Logic_of_graphs dbr:Arthur–Merlin_protocol dbr:Hidden_subgroup_problem dbr:Brian_Alspach dbr:Graph_matching dbr:Exact_graph_matching dbr:GI-complete
is owl:differentFrom of	dbr:Group_isomorphism_problem
is foaf:primaryTopic of	wikipedia-en:Graph_isomorphism_problem