Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Bakers_technique> ?p ?o }
Showing triples 1 to 46 of
46
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. Bidimensionality theory of Erik Demaine, Fedor Fomin, Hajiaghayi, and Dimitrios Thilikos and its offshoot simplifying decompositions (Demaine, Hajiaghayi & Kawarabayashi (2005),Demaine, Hajiaghayi & Kawarabayashi (2011)) generalizes and greatly expands the applicability of Baker's techniquefor a vast set of problems on planar graphs and more generally graphs excluding a fixed minor and beyond.".
- Bakers_technique wikiPageID "33187484".
- Bakers_technique wikiPageLength "5485".
- Bakers_technique wikiPageOutDegree "20".
- Bakers_technique wikiPageRevisionID "698509751".
- Bakers_technique wikiPageWikiLink 1-planar_graph.
- Bakers_technique wikiPageWikiLink Bidimensionality.
- 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 Erik_Demaine.
- Bakers_technique wikiPageWikiLink Graph_minor.
- Bakers_technique wikiPageWikiLink Independent_set.
- Bakers_technique wikiPageWikiLink Independent_set_(graph_theory).
- Bakers_technique wikiPageWikiLink Mohammad_Hajiaghayi.
- Bakers_technique wikiPageWikiLink Outerplanar_graph.
- Bakers_technique wikiPageWikiLink Planar_graph.
- Bakers_technique wikiPageWikiLink Polynomial-time_approximation_scheme.
- Bakers_technique wikiPageWikiLink Subgraph_isomorphism_problem.
- Bakers_technique wikiPageWikiLink Vertex_cover.
- Bakers_technique wikiPageWikiLinkText "Baker's technique".
- Bakers_technique wikiPageUsesTemplate Template:Citation.
- Bakers_technique wikiPageUsesTemplate Template:Harvtxt.
- 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 type Algorithm.
- Bakers_technique type Combinatoric.
- Bakers_technique type Field.
- Bakers_technique type Redirect.
- Bakers_technique type Relation.
- 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 Q4849086.
- Bakers_technique sameAs m.0hr5tbt.
- Bakers_technique sameAs Q4849086.
- Bakers_technique wasDerivedFrom Bakers_technique?oldid=698509751.
- Bakers_technique isPrimaryTopicOf Bakers_technique.