Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Forbidden_graph_characterization> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- Forbidden_graph_characterization abstract "A forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures.Families vary in the nature of what is forbidden. In general, a structure G is a member of a family if and only if a forbidden substructure is not contained in G. The forbidden substructure might simply be a subgraph, or a substructure from which one might derive (via, e.g., edge contraction or subdivision) that which is forbidden. Thus, the forbidden structure might be one of: subgraphs, homeomorphic subgraphs (also called topological minors). induced subgraphs, graph minors,Such forbidden structures can also be called obstruction sets.Forbidden graph characterizations are utilized in combinatorial algorithms, often for identifying a structure. Such methods can provide a polynomial-time algorithm for determining a graph's membership in a specific family (i.e., a polynomial-time implementation of an indicator function). A well-known characterization of this kind is Kuratowski's theorem that provides two forbidden homeomorphic subgraphs, using which, one may determine a graph's planarity. Another is the Robertson–Seymour theorem that proves the existence of a forbidden minor characterization for several graph families.".
- Forbidden_graph_characterization wikiPageExternalLink books?id=04YbQF8oscQC&lpg=PA327&pg=PA107.
- Forbidden_graph_characterization wikiPageExternalLink books?id=04YbQF8oscQC&lpg=PA327&pg=PA327.
- Forbidden_graph_characterization wikiPageExternalLink books?id=NvRXJSl9hUUC&pg=RA1-PA275&vq=forbidden&dq=%22hereditary+property%22+forbidden.
- Forbidden_graph_characterization wikiPageID "13547826".
- Forbidden_graph_characterization wikiPageRevisionID "606142679".
- Forbidden_graph_characterization hasPhotoCollection Forbidden_graph_characterization.
- Forbidden_graph_characterization subject Category:Graph_families.
- Forbidden_graph_characterization subject Category:Graph_minor_theory.
- Forbidden_graph_characterization subject Category:Graph_theory.
- Forbidden_graph_characterization subject Category:Hypergraphs.
- Forbidden_graph_characterization type Abstraction100002137.
- Forbidden_graph_characterization type Family108078020.
- Forbidden_graph_characterization type GraphFamilies.
- Forbidden_graph_characterization type Group100031264.
- Forbidden_graph_characterization type Organization108008335.
- Forbidden_graph_characterization type SocialGroup107950920.
- Forbidden_graph_characterization type Unit108189659.
- Forbidden_graph_characterization type YagoLegalActor.
- Forbidden_graph_characterization type YagoLegalActorGeo.
- Forbidden_graph_characterization type YagoPermanentlyLocatedEntity.
- Forbidden_graph_characterization comment "A forbidden graph characterization is a method of specifying a family of graph, or hypergraph, structures.Families vary in the nature of what is forbidden. In general, a structure G is a member of a family if and only if a forbidden substructure is not contained in G. The forbidden substructure might simply be a subgraph, or a substructure from which one might derive (via, e.g., edge contraction or subdivision) that which is forbidden.".
- Forbidden_graph_characterization label "Forbidden graph characterization".
- Forbidden_graph_characterization sameAs m.03c90l8.
- Forbidden_graph_characterization sameAs Q5467387.
- Forbidden_graph_characterization sameAs Q5467387.
- Forbidden_graph_characterization sameAs Forbidden_graph_characterization.
- Forbidden_graph_characterization wasDerivedFrom Forbidden_graph_characterization?oldid=606142679.
- Forbidden_graph_characterization isPrimaryTopicOf Forbidden_graph_characterization.