This HTML5 document contains 71 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n4http://www-math.mit.edu/~hajiagha/
n19https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Baker's_Technique
dbo:wikiPageWikiLink
dbr:Baker's_technique
dbo:wikiPageRedirects
dbr:Baker's_technique
Subject Item
dbr:Brenda_Baker
dbo:wikiPageWikiLink
dbr:Baker's_technique
Subject Item
dbr:Intersection_number_(graph_theory)
dbo:wikiPageWikiLink
dbr:Baker's_technique
Subject Item
dbr:Penny_graph
dbo:wikiPageWikiLink
dbr:Baker's_technique
Subject Item
dbr:1-planar_graph
dbo:wikiPageWikiLink
dbr:Baker's_technique
Subject Item
dbr:Clique_cover
dbo:wikiPageWikiLink
dbr:Baker's_technique
Subject Item
dbr:K-outerplanar_graph
dbo:wikiPageWikiLink
dbr:Baker's_technique
Subject Item
dbr:Baker's_technique
rdf:type
yago:YagoPermanentlyLocatedEntity yago:Act100030358 yago:Algorithm105847438 yago:Procedure101023820 yago:Abstraction100002137 dbo:Software yago:VisualCommunication106873252 yago:WikicatPlanarGraphs yago:Event100029378 yago:Communication100033020 yago:Graph107000195 yago:WikicatApproximationAlgorithms yago:Activity100407535 yago:Rule105846932 yago:PsychologicalFeature100023100
rdfs:label
Техника Бренды Бейкер Baker's technique Техніка Бренди Бейкер
rdfs:comment
Техника Бренды Бейкер — это метод построения приближенных схем полиномиального времени (ПСПВ, PTAS) для задач на планарных графах. Метод назван именем американской учёной в области информатики , сообщившей о методе на конференции 1983 года и опубликовавшей статью в журнале Journal of the ACM в 1994. In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the Journal of the ACM in 1994.
dcterms:subject
dbc:Planar_graphs dbc:Approximation_algorithms dbc:1983_in_computing
dbo:wikiPageID
33187484
dbo:wikiPageRevisionID
1032191740
dbo:wikiPageWikiLink
dbr:Brenda_Baker dbr:Minimum_dominating_set dbr:Independent_set_(graph_theory) dbr:Maximum_independent_set dbr:Mohammad_Hajiaghayi dbr:Bidimensionality dbr:1-planar_graph dbr:Erik_Demaine dbr:Theoretical_computer_science dbr:K-outerplanar_graph dbr:Subgraph_isomorphism dbc:Approximation_algorithms dbc:Planar_graphs dbr:Dynamic_programming dbc:1983_in_computing dbr:Graph_minor dbr:Planar_graph dbr:Edge_dominating_set dbr:Journal_of_the_ACM dbr:Polynomial-time_approximation_scheme dbr:Minimum_vertex_cover
dbo:wikiPageExternalLink
n4:graphminoralgorithm.pdf
owl:sameAs
yago-res:Baker's_technique dbpedia-uk:Техніка_Бренди_Бейкер dbpedia-ru:Техника_Бренды_Бейкер freebase:m.0hr5tbt wikidata:Q4849086 n19:4VHoJ
dbp:wikiPageUsesTemplate
dbt:Citation dbt:Harvtxt dbt:Refbegin
dbo:abstract
In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the Journal of the ACM in 1994. 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. 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. The bidimensionality theory of Erik Demaine, Fedor Fomin, Hajiaghayi, and Dimitrios Thilikos and its offshoot simplifying decompositions 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, such as bounded genus graphs, as well as to other classes of graphs not closed under taking minors such as the 1-planar graphs. Техника Бренды Бейкер — это метод построения приближенных схем полиномиального времени (ПСПВ, PTAS) для задач на планарных графах. Метод назван именем американской учёной в области информатики , сообщившей о методе на конференции 1983 года и опубликовавшей статью в журнале Journal of the ACM в 1994. Идея техники Бренды Бейкер заключается в разбиении графа на уровни, так что задача может быть решена оптимально на каждом уровне, затем решения на каждом уровне комбинируются удовлетворительным способом, что приводит к реалистичному решению. Эта техника дала ПСПВ для следующих задач: задача поиска изоморфного подграфа, задача о максимальном независимом множестве, задача о вершинном покрытии, минимальное доминирующее множество, минимальное доминирующее множество рёбер многие другие. Теория двумерности Эрика Демайна, Фёдора Фомина, Мухаммеда Хаджигайи и Димитроса Тиликоса и её ответление упрощённые декомпозиции обобщает и существенно расширяет область применения техники Бренды Бейкер на обширное множество задач на планарных графах и, более обще, на графах, не содержащих определённого минора, таких как графы с ограниченным родом, а также другие классы графов, не замкнутые по взятию минора, такие как 1-планарные графы.
gold:hypernym
dbr:Method
prov:wasDerivedFrom
wikipedia-en:Baker's_technique?oldid=1032191740&ns=0
dbo:wikiPageLength
6335
foaf:isPrimaryTopicOf
wikipedia-en:Baker's_technique
Subject Item
wikipedia-en:Baker's_technique
foaf:primaryTopic
dbr:Baker's_technique