| Property |
Value |
| dbo:abstract
|
- En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation. (fr)
- En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation. (fr)
|
| dbo:isPartOf
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 17302 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1995 (xsd:integer)
- 2000 (xsd:integer)
- 2003 (xsd:integer)
- 2005 (xsd:integer)
- 2007 (xsd:integer)
- 2008 (xsd:integer)
- 2013 (xsd:integer)
|
| prop-fr:auteur
| |
| prop-fr:consultéLe
| |
| prop-fr:date
| |
| prop-fr:doi
|
- 10.100700 (xsd:double)
- 10.113700 (xsd:double)
- 10.114500 (xsd:double)
|
| prop-fr:fr
|
- méthode des probabilités conditionnelles (fr)
- méthode des probabilités conditionnelles (fr)
|
| prop-fr:isbn
| |
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Michel Goemans (fr)
- Michel Goemans (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Young (fr)
- Newman (fr)
- Williamson (fr)
- Meunier (fr)
- Kann (fr)
- Kindler (fr)
- Ausiello (fr)
- Crescenzi (fr)
- Gambosi (fr)
- Marchetti-Spaccamela (fr)
- Protasi (fr)
- O'Donnell (fr)
- Sebo (fr)
- Goemans (fr)
- Khuller (fr)
- Mitzenmacher (fr)
- Mossel (fr)
- Raghavachari (fr)
- Upfal (fr)
- Young (fr)
- Newman (fr)
- Williamson (fr)
- Meunier (fr)
- Kann (fr)
- Kindler (fr)
- Ausiello (fr)
- Crescenzi (fr)
- Gambosi (fr)
- Marchetti-Spaccamela (fr)
- Protasi (fr)
- O'Donnell (fr)
- Sebo (fr)
- Goemans (fr)
- Khuller (fr)
- Mitzenmacher (fr)
- Mossel (fr)
- Raghavachari (fr)
- Upfal (fr)
|
| prop-fr:numéro
|
- 1 (xsd:integer)
- 6 (xsd:integer)
|
| prop-fr:pages
| |
| prop-fr:passage
| |
| prop-fr:prénom
|
- Michael (fr)
- Frédéric (fr)
- Marco (fr)
- Alberto (fr)
- Guy (fr)
- Giorgio (fr)
- Ryan (fr)
- Eli (fr)
- Andras (fr)
- Pierluigi (fr)
- Samir (fr)
- Viggo (fr)
- David P. (fr)
- Alantha (fr)
- Balaji (fr)
- Elchanan (fr)
- Michel X. (fr)
- Neal E. (fr)
- Michael (fr)
- Frédéric (fr)
- Marco (fr)
- Alberto (fr)
- Guy (fr)
- Giorgio (fr)
- Ryan (fr)
- Eli (fr)
- Andras (fr)
- Pierluigi (fr)
- Samir (fr)
- Viggo (fr)
- David P. (fr)
- Alantha (fr)
- Balaji (fr)
- Elchanan (fr)
- Michel X. (fr)
- Neal E. (fr)
|
| prop-fr:périodique
| |
| prop-fr:site
| |
| prop-fr:titre
|
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming (fr)
- Le découpage des graphes (fr)
- Mathématiques, l'explosion continue (fr)
- Maximum Cut (fr)
- Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? (fr)
- Probability and Computing: Randomized Algorithms and Probabilistic Analysis (fr)
- Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (fr)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming (fr)
- Le découpage des graphes (fr)
- Mathématiques, l'explosion continue (fr)
- Maximum Cut (fr)
- Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? (fr)
- Probability and Computing: Randomized Algorithms and Probabilistic Analysis (fr)
- Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (fr)
|
| prop-fr:titreChapitre
|
- Greedy methods (fr)
- Max cut (fr)
- Parcours et coupes (fr)
- Greedy methods (fr)
- Max cut (fr)
- Parcours et coupes (fr)
|
| prop-fr:titreOuvrage
|
- Encyclopedia of Algorithms (fr)
- Handbook of Approximation Algorithms and Metaheuristics (fr)
- Graphes et applications-vol. 2 (fr)
- Encyclopedia of Algorithms (fr)
- Handbook of Approximation Algorithms and Metaheuristics (fr)
- Graphes et applications-vol. 2 (fr)
|
| prop-fr:trad
|
- Method of conditional probabilities (fr)
- Method of conditional probabilities (fr)
|
| prop-fr:url
| |
| prop-fr:volume
|
- 37 (xsd:integer)
- 42 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Cambridge (fr)
- Springer (fr)
- Chapman (fr)
- FSMP, SFS, SMF, SMAI (fr)
- JC Fournier (fr)
- Cambridge (fr)
- Springer (fr)
- Chapman (fr)
- FSMP, SFS, SMF, SMAI (fr)
- JC Fournier (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation. (fr)
- En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation. (fr)
|
| rdfs:label
|
- Coupe maximum (fr)
- Максимальный разрез графа (ru)
- Coupe maximum (fr)
- Максимальный разрез графа (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
