| dbo:abstract
|
- In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by .It is considered the archetype of algorithmic meta-theorems. (en)
- En algorithmique et en théorie de la complexité, le théorème de Courcelle est le suivant : Théorème de Courcelle — Toute propriété de la logique monadique du second ordre est décidable en temps linéaire dans la classe des graphes avec une largeur arborescente bornée. C'est un métathéorème, dans le sens où il concerne une classe de problèmes algorithmiques. Le théorème est dû à Bruno Courcelle. Dans le contexte de ce théorème, un graphe est donné par un ensemble de sommets et une relation d'adjacence , et la restriction à la logique monadique signifie que la propriété étudiée peut contenir des quantificateurs sur des ensembles de sommets (quantificateurs du second ordre sur des prédicats monadiques), mais pas de quantificateurs sur des ensembles d'arcs (ces quantificateurs du second ordre porteraient sur des prédicats binaires). (fr)
- Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в , может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.Результат считается прототипом алгоритмических метатеорем. (ru)
- Теоре́ма Курселя — твердження про те, що будь-яку властивість графа, що визначається в , можна встановити за лінійний час на графах з обмеженою деревною шириною. Результат уперше довів 1990 року і незалежно перевідкрили Борі, Паркер і Товей. Результат вважають прототипом алгоритмічних метатеорем. (uk)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 24719 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by .It is considered the archetype of algorithmic meta-theorems. (en)
- Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в , может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.Результат считается прототипом алгоритмических метатеорем. (ru)
- Теоре́ма Курселя — твердження про те, що будь-яку властивість графа, що визначається в , можна встановити за лінійний час на графах з обмеженою деревною шириною. Результат уперше довів 1990 року і незалежно перевідкрили Борі, Паркер і Товей. Результат вважають прототипом алгоритмічних метатеорем. (uk)
- En algorithmique et en théorie de la complexité, le théorème de Courcelle est le suivant : Théorème de Courcelle — Toute propriété de la logique monadique du second ordre est décidable en temps linéaire dans la classe des graphes avec une largeur arborescente bornée. (fr)
|
| rdfs:label
|
- Courcelles Theorem (de)
- Courcelle's theorem (en)
- Théorème de Courcelle (fr)
- Теорема Курселя (ru)
- Теорема Курселя (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
