About: Subgraph isomorphism problem

Property	Value
dbo:description	the NP-complete problem of testing whether one graph is a subgraph of another (en) NP-повна задача перевірки того, чи є один граф підграфом іншого (uk)
dbo:thumbnail	wiki-commons:Special:FilePath/Subgraph_isomorphism.svg?width=300
dbo:wikiPageExternalLink	http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf http://4mhz.de/cook.html%7Cdoi=10.1145/800157.805047%7Ctitle-link=Symposium http://www.cs.brown.edu/publications/jgaa/accepted/99/Eppstein99.3.3.pdf%7Carxiv=cs.DS/9911003%7Cdoi=10.7155/jgaa.00014
dbo:wikiPageWikiLink	dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory dbr:Hamiltonian_cycle dbr:Glossary_of_graph_theory dbr:Undirected_graph dbr:Hamiltonian_path_problem dbr:Artificial_intelligence dbc:Graph_algorithms dbr:Graph_isomorphism dbr:Social_network dbr:Induced_subgraph_isomorphism_problem dbr:Clique_problem dbr:Theoretical_computer_science dbr:Bioinformatics dbr:Complete_graph dbr:Cheminformatics dbr:Journal_of_the_ACM dbr:Graph_isomorphism_problem dbr:Structure_editor dbr:Bijection dbr:Computer-aided_design dbr:Graph_rewriting dbr:Pattern_matching dbr:Structure_mining dbr:Aanderaa–Karp–Rosenberg_conjecture dbr:Planar_graphs dbr:Planar_graph dbr:Decision_problem dbr:Bounded_expansion dbr:Frequent_subtree_mining dbr:NP-complete dbr:Linear_time dbr:Journal_of_Graph_Algorithms_and_Applications dbr:Query_complexity dbr:Smiles_arbitrary_target_specification dbr:Electronic_circuits dbr:Maximum_common_edge_subgraph_problem dbr:Maximum_common_subgraph_isomorphism_problem dbr:Polynomial-time_many-one_reduction dbr:SMILES dbr:Exponential_random_graph dbr:Journal_of_Experimental_Algorithmics
dbp:wikiPageUsesTemplate	dbt:Authority_control dbt:Reflist dbt:Citation dbt:Harvtxt dbt:Broader dbt:Short_description
dct:subject	dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory dbc:Graph_algorithms
gold:hypernym	dbr:Task
rdf:type	owl:Thing
rdfs:label	Subgraph isomorphism problem (en) Problema de isomorfismo de subgrafos (es) Problème de l'isomorphisme de sous-graphes (fr) Isomorfismo di sottografi (it) Problem izomorfizmu podgrafu (pl) Задача поиска изоморфного подграфа (ru) Problema do isomorfismo de subgrafos (pt) Задача пошуку ізоморфного підграфа (uk)
owl:sameAs	freebase:Subgraph isomorphism problem yago-res:Subgraph isomorphism problem wikidata:Subgraph isomorphism problem dbpedia-it:Subgraph isomorphism problem dbpedia-fr:Subgraph isomorphism problem dbpedia-pt:Subgraph isomorphism problem dbpedia-es:Subgraph isomorphism problem dbpedia-ru:Subgraph isomorphism problem dbpedia-vi:Subgraph isomorphism problem dbpedia-pl:Subgraph isomorphism problem dbpedia-sr:Subgraph isomorphism problem dbpedia-uk:Subgraph isomorphism problem dbpedia-global:Subgraph isomorphism problem
prov:wasDerivedFrom	wikipedia-en:Subgraph_isomorphism_problem?oldid=1295790205&ns=0
foaf:depiction	wiki-commons:Special:FilePath/Subgraph_isomorphism.svg
foaf:isPrimaryTopicOf	wikipedia-en:Subgraph_isomorphism_problem
is dbo:wikiPageRedirects of	dbr:Substructure_search dbr:Methods_for_solving_subgraph_isomorphism_problems dbr:Algorithms_for_solving_subgraph_isomorphism_problems dbr:Subgraph_isomorphism dbr:Subgraph_matching
is dbo:wikiPageWikiLink of	dbr:NP-completeness dbr:List_of_NP-complete_problems dbr:NP_(complexity) dbr:Graph_isomorphism dbr:Matching_(graph_theory) dbr:Forbidden_subgraph_problem dbr:Maximum_common_edge_subgraph dbr:Maximum_common_induced_subgraph dbr:Induced_subgraph_isomorphism_problem dbr:Graph-tool dbr:Graph_theory dbr:Induced_subgraph dbr:Graph_isomorphism_problem dbr:Graph_rewriting dbr:List_of_algorithms dbr:Structured_program_theorem dbr:Bounded_expansion dbr:Logic_of_graphs dbr:Frequent_subtree_mining dbr:Graph_removal_lemma dbr:Graph_matching dbr:Substructure_search dbr:Methods_for_solving_subgraph_isomorphism_problems dbr:Algorithms_for_solving_subgraph_isomorphism_problems dbr:Subgraph_isomorphism dbr:Subgraph_matching
is foaf:primaryTopic of	wikipedia-en:Subgraph_isomorphism_problem