Matches in DBpedia 2015-10 for { <http://dbpedia.org/resource/Bakers_technique> ?p ?o }
Showing triples 1 to 41 of
41
with 100 triples per page.
- Bakers_technique abstract "Baker's technique, created in 1983 (conference presentation) and published in a journal in 1994 by Brenda Baker, is a method for designing polynomial-time approximation schemes, PTASs, for problems on planar graphs. This technique has given PTASs for the following problems: subgraph isomorphism, maximum independent set, minimum vertex cover, minimum dominating set, minimum edge dominating set, maximum triangle matching, and many others. Its generalizations have also led to many PTASs on graphs excluding a fixed minor, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the 1-planar graphs. The idea for Baker's technique is to break the graph into layers, such that the problem can be solved optimally on each layer, then combine the solutions from each layer in a reasonable way that will result in a feasible solution.".
- Bakers_technique wikiPageID "33187484".
- Bakers_technique wikiPageLength "4651".
- Bakers_technique wikiPageOutDegree "15".
- Bakers_technique wikiPageRevisionID "678819867".
- Bakers_technique wikiPageWikiLink 1-planar_graph.
- Bakers_technique wikiPageWikiLink Category:Approximation_algorithms.
- Bakers_technique wikiPageWikiLink Category:Articles_created_via_the_Article_Wizard.
- Bakers_technique wikiPageWikiLink Category:Graph_theory.
- Bakers_technique wikiPageWikiLink Category:Planar_graphs.
- Bakers_technique wikiPageWikiLink Dominating_set.
- Bakers_technique wikiPageWikiLink Dynamic_programming.
- Bakers_technique wikiPageWikiLink Edge_dominating_set.
- Bakers_technique wikiPageWikiLink Independent_set.
- Bakers_technique wikiPageWikiLink Independent_set_(graph_theory).
- Bakers_technique wikiPageWikiLink Maximum_independent_set.
- Bakers_technique wikiPageWikiLink Minimum_dominating_set.
- Bakers_technique wikiPageWikiLink Minimum_vertex_cover.
- Bakers_technique wikiPageWikiLink Outerplanar_graph.
- Bakers_technique wikiPageWikiLink Planar_graph.
- Bakers_technique wikiPageWikiLink Polynomial-time_approximation_scheme.
- Bakers_technique wikiPageWikiLink Subgraph_isomorphism.
- Bakers_technique wikiPageWikiLink Subgraph_isomorphism_problem.
- Bakers_technique wikiPageWikiLink Vertex_cover.
- Bakers_technique wikiPageWikiLinkText "Baker's technique".
- Bakers_technique hasPhotoCollection Bakers_technique.
- Bakers_technique wikiPageUsesTemplate Template:Citation.
- Bakers_technique wikiPageUsesTemplate Template:Refbegin.
- Bakers_technique subject Category:Approximation_algorithms.
- Bakers_technique subject Category:Articles_created_via_the_Article_Wizard.
- Bakers_technique subject Category:Graph_theory.
- Bakers_technique subject Category:Planar_graphs.
- Bakers_technique hypernym Method.
- Bakers_technique type Software.
- Bakers_technique comment "Baker's technique, created in 1983 (conference presentation) and published in a journal in 1994 by Brenda Baker, is a method for designing polynomial-time approximation schemes, PTASs, for problems on planar graphs. This technique has given PTASs for the following problems: subgraph isomorphism, maximum independent set, minimum vertex cover, minimum dominating set, minimum edge dominating set, maximum triangle matching, and many others.".
- Bakers_technique label "Baker's technique".
- Bakers_technique sameAs m.0hr5tbt.
- Bakers_technique sameAs Q4849086.
- Bakers_technique sameAs Q4849086.
- Bakers_technique wasDerivedFrom Bakers_techniqueoldid=678819867.
- Bakers_technique isPrimaryTopicOf Bakers_technique.