| Property |
Value |
| dbo:abstract
|
- En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier. La réduction se place dans le cadre de la complexité paramétrée. La réduction est possible quand une instance d'un problème possède des parties qui sont facilement décidables et détectables, et que l'on peut enlever sans modifier le problème de départ. Les données qui subsistent après ces réductions forment le noyau de l'instance. (fr)
- En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier. La réduction se place dans le cadre de la complexité paramétrée. La réduction est possible quand une instance d'un problème possède des parties qui sont facilement décidables et détectables, et que l'on peut enlever sans modifier le problème de départ. Les données qui subsistent après ces réductions forment le noyau de l'instance. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13469 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1999 (xsd:integer)
- 2006 (xsd:integer)
- 2009 (xsd:integer)
- 2010 (xsd:integer)
- 2011 (xsd:integer)
- 2013 (xsd:integer)
- 2015 (xsd:integer)
|
| prop-fr:auteur
|
- Daniel Lokshtanov (fr)
- Daniel Marx (fr)
- Fedor V. Fomin (fr)
- Marcin Pilipczuk (fr)
- Marek Cygan (fr)
- Michał Pilipczuk (fr)
- Saket Saurabh (fr)
- Łukasz Kowalik (fr)
- Daniel Lokshtanov (fr)
- Daniel Marx (fr)
- Fedor V. Fomin (fr)
- Marcin Pilipczuk (fr)
- Marek Cygan (fr)
- Michał Pilipczuk (fr)
- Saket Saurabh (fr)
- Łukasz Kowalik (fr)
|
| prop-fr:doi
|
- 10.100700 (xsd:double)
- 10.101600 (xsd:double)
- 10.114500 (xsd:double)
|
| prop-fr:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:journal
| |
| prop-fr:lienAuteur
|
- Rod Downey (fr)
- Hans L. Bodlaender (fr)
- Michael Fellows (fr)
- Rod Downey (fr)
- Hans L. Bodlaender (fr)
- Michael Fellows (fr)
|
| prop-fr:mathReviews
|
- 1656112 (xsd:integer)
- 3154461 (xsd:integer)
|
| prop-fr:nom
|
- Downey (fr)
- Hermelin (fr)
- Bodlaender (fr)
- Fellows (fr)
- Grohe (fr)
- Niedermeier (fr)
- Thomassé (fr)
- Flum (fr)
- Lampis (fr)
- Downey (fr)
- Hermelin (fr)
- Bodlaender (fr)
- Fellows (fr)
- Grohe (fr)
- Niedermeier (fr)
- Thomassé (fr)
- Flum (fr)
- Lampis (fr)
|
| prop-fr:numéro
|
- 2 (xsd:integer)
- 8 (xsd:integer)
- 23 (xsd:integer)
|
| prop-fr:numéroDansCollection
| |
| prop-fr:pages
|
- 423 (xsd:integer)
- 1089 (xsd:integer)
|
| prop-fr:pagesTotales
|
- xi+300 (fr)
- xiii+495 (fr)
- xvii+613 (fr)
- xxx+763 (fr)
- xi+300 (fr)
- xiii+495 (fr)
- xvii+613 (fr)
- xxx+763 (fr)
|
| prop-fr:prénom
|
- Michael (fr)
- Martin (fr)
- Danny (fr)
- Rolf (fr)
- Jörg (fr)
- Stéphan (fr)
- Hans L. (fr)
- Michael R. (fr)
- Rod G. (fr)
- Rodney G. (fr)
- Michael (fr)
- Martin (fr)
- Danny (fr)
- Rolf (fr)
- Jörg (fr)
- Stéphan (fr)
- Hans L. (fr)
- Michael R. (fr)
- Rod G. (fr)
- Rodney G. (fr)
|
| prop-fr:présentationEnLigne
| |
| prop-fr:sudoc
| |
| prop-fr:série
|
- Monographs in Computer Science (fr)
- Oxford Lecture Series in Mathematics and its Applications (fr)
- Monographs in Computer Science (fr)
- Oxford Lecture Series in Mathematics and its Applications (fr)
|
| prop-fr:titre
|
- Fundamentals of Parameterized Complexity (fr)
- Invitation to Fixed-Parameter Algorithms (fr)
- Parameterized Complexity Theory (fr)
- A 4k2 kernel for feedback vertex set (fr)
- On problems without polynomial kernels (fr)
- Parameterized Complexity (fr)
- Parametrized Algorithms (fr)
- A kernel of order 2k − c log k for vertex cover (fr)
- Fundamentals of Parameterized Complexity (fr)
- Invitation to Fixed-Parameter Algorithms (fr)
- Parameterized Complexity Theory (fr)
- A 4k2 kernel for feedback vertex set (fr)
- On problems without polynomial kernels (fr)
- Parameterized Complexity (fr)
- Parametrized Algorithms (fr)
- A kernel of order 2k − c log k for vertex cover (fr)
|
| prop-fr:volume
|
- 6 (xsd:integer)
- 75 (xsd:integer)
- 111 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier. La réduction se place dans le cadre de la complexité paramétrée. La réduction est possible quand une instance d'un problème possède des parties qui sont facilement décidables et détectables, et que l'on peut enlever sans modifier le problème de départ. Les données qui subsistent après ces réductions forment le noyau de l'instance. (fr)
- En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier. La réduction se place dans le cadre de la complexité paramétrée. La réduction est possible quand une instance d'un problème possède des parties qui sont facilement décidables et détectables, et que l'on peut enlever sans modifier le problème de départ. Les données qui subsistent après ces réductions forment le noyau de l'instance. (fr)
|
| rdfs:label
|
- Kernelisation (fr)
- Параметрическая редукция (ru)
- Kernelisation (fr)
- Параметрическая редукция (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
