| dbo:abstract |
In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph. (en) Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного графа как порождённого подграфа другого, большего графа. (ru) |
| dbo:wikiPageID |
6892618 (xsd:integer) |
| dbo:wikiPageLength |
5128 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1032210372 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Hypercube_graph dbr:Decision_problem dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbc:NP-complete_problems dbr:NP-complete dbr:Snake-in-the-box dbr:Clique_(graph_theory) dbr:Computational_complexity_theory dbr:Path_(graph_theory) dbr:K-vertex-connected_graph dbr:Outerplanar_graph dbr:Graph_isomorphism dbr:Graph_theory dbc:Computational_problems_in_graph_theory dbr:Polynomial_time dbr:Maximum_clique_problem dbr:Injective_function dbr:Subgraph_isomorphism_problem dbr:Series–parallel_graph dbr:Maximum_independent_set_problem |
| dbp:wikiPageUsesTemplate |
dbt:Reflist dbt:Snakes_and_coils_in_the_box.svg |
| dct:subject |
dbc:NP-complete_problems dbc:Computational_problems_in_graph_theory |
| gold:hypernym |
dbr:Problem |
| rdf:type |
yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 dbo:Disease yago:State100024720 |
| rdfs:comment |
In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph. (en) Задача изоморфизма порождённому подграфу является NP-полной задачей разрешимости в теории сложности и теории графов. Задача заключается в поиске данного графа как порождённого подграфа другого, большего графа. (ru) |
| rdfs:label |
Induced subgraph isomorphism problem (en) Задача изоморфизма порождённому подграфу (ru) |
| owl:sameAs |
freebase:Induced subgraph isomorphism problem yago-res:Induced subgraph isomorphism problem wikidata:Induced subgraph isomorphism problem dbpedia-ru:Induced subgraph isomorphism problem https://global.dbpedia.org/id/4nVdj |
| prov:wasDerivedFrom |
wikipedia-en:Induced_subgraph_isomorphism_problem?oldid=1032210372&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Induced_subgraph_isomorphism_problem |
| is dbo:wikiPageWikiLink of |
dbr:Induced_subgraph dbr:Snake-in-the-box dbr:Maximum_common_edge_subgraph dbr:Subgraph_isomorphism_problem |
| is foaf:primaryTopic of |
wikipedia-en:Induced_subgraph_isomorphism_problem |
