Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Baker's_technique> ?p ?o. }
Showing items 1 to 21 of
21
with 100 items per page.
- Baker's_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.".
- Baker's_technique wikiPageID "33187484".
- Baker's_technique wikiPageRevisionID "603485042".
- Baker's_technique hasPhotoCollection Baker's_technique.
- Baker's_technique subject Category:Approximation_algorithms.
- Baker's_technique subject Category:Articles_created_via_the_Article_Wizard.
- Baker's_technique subject Category:Graph_theory.
- Baker's_technique subject Category:Planar_graphs.
- Baker's_technique type Abstraction100002137.
- Baker's_technique type Communication100033020.
- Baker's_technique type Graph107000195.
- Baker's_technique type PlanarGraphs.
- Baker's_technique type VisualCommunication106873252.
- Baker's_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.".
- Baker's_technique label "Baker's technique".
- Baker's_technique sameAs m.0hr5tbt.
- Baker's_technique sameAs Q4849086.
- Baker's_technique sameAs Q4849086.
- Baker's_technique sameAs Baker's_technique.
- Baker's_technique wasDerivedFrom Baker's_technique?oldid=603485042.
- Baker's_technique isPrimaryTopicOf Baker's_technique.