| http://dbpedia.org/ontology/abstract
|
En théorie des graphes et en algorithmique … 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.mment dans le contexte de l'approximation.
|
| http://dbpedia.org/ontology/isPartOf
|
http://fr.dbpedia.org/resource/21_probl%C3%A8mes_NP-complets_de_Karp +
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Max-cut.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.liafa.jussieu.fr/~nschaban/publications/2012/2012-Maths-PansuSchabanel.pdf +
, http://cermics.enpc.fr/~meuniefr/hermes13dec.pdf +
, http://images.math.cnrs.fr/Le-decoupage-des-graphes.html +
, http://www.nada.kth.se/~viggo/wwwcompendium/node85.html +
, http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/ +
|
| http://dbpedia.org/ontology/wikiPageID
|
7755716
|
| http://dbpedia.org/ontology/wikiPageLength
|
17302
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
185260106
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://fr.dbpedia.org/resource/Th%C3%A9orie_de_l%27ordonnancement +
, http://fr.dbpedia.org/resource/Luca_Trevisan +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Probl%C3%A8me_NP-complet +
, http://fr.dbpedia.org/resource/Coupe_%28th%C3%A9orie_des_graphes%29 +
, http://fr.dbpedia.org/resource/Physique_th%C3%A9orique +
, http://fr.dbpedia.org/resource/Physique_statistique +
, http://fr.dbpedia.org/resource/Gerhard_Woeginger +
, http://fr.dbpedia.org/resource/Sch%C3%A9ma_d%27approximation_en_temps_polynomial +
, http://fr.dbpedia.org/resource/Algorithme_de_fouille_de_flots_de_donn%C3%A9es +
, http://fr.dbpedia.org/resource/Mod%C3%A8le_d%27Ising +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Concept_en_th%C3%A9orie_des_graphes +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_de_satisfaction_de_contraintes +
, http://fr.dbpedia.org/resource/R%C3%A9duction_%28complexit%C3%A9%29 +
, http://fr.dbpedia.org/resource/Michel_Goemans +
, http://fr.dbpedia.org/resource/Th%C3%A9or%C3%A8me_flot-max/coupe-min +
, http://fr.dbpedia.org/resource/Graphe_cordal +
, http://fr.dbpedia.org/resource/Fichier:Max-cut.svg +
, http://fr.dbpedia.org/resource/Algorithme_probabiliste +
, http://fr.dbpedia.org/resource/Algorithmique +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_du_sac_%C3%A0_dos +
, http://fr.dbpedia.org/resource/APX_%28complexit%C3%A9%29 +
, http://fr.dbpedia.org/resource/S%C3%A9quen%C3%A7age_de_t%C3%A2ches +
, http://fr.dbpedia.org/resource/M%C3%A9thode_des_poids_multiplicatifs +
, http://fr.dbpedia.org/resource/Images_des_math%C3%A9matiques +
, http://fr.dbpedia.org/resource/Journal_of_the_ACM +
, http://fr.dbpedia.org/resource/P_%28complexit%C3%A9%29 +
, http://fr.dbpedia.org/resource/Th%C3%A9orie_spectrale_des_graphes +
, http://fr.dbpedia.org/resource/D%C3%A9randomisation +
, http://fr.dbpedia.org/resource/Conjecture_des_jeux_uniques +
, http://fr.dbpedia.org/resource/Subhash_Khot +
, http://fr.dbpedia.org/resource/Coupe_minimum +
, http://fr.dbpedia.org/resource/Th%C3%A9orie_des_graphes +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_P_%E2%89%9F_NP +
, http://fr.dbpedia.org/resource/Marek_Karpinski +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_NP-complet +
, http://fr.dbpedia.org/resource/Algorithme_d%27approximation +
, http://fr.dbpedia.org/resource/Algorithme_d%27Edmonds_pour_les_couplages +
, http://fr.dbpedia.org/resource/Densit%C3%A9_d%27un_graphe +
, http://fr.dbpedia.org/resource/Graphe_planaire +
, http://fr.dbpedia.org/resource/Spin +
, http://fr.dbpedia.org/resource/Graphe_scind%C3%A9 +
, http://fr.dbpedia.org/resource/21_probl%C3%A8mes_NP-complets_de_Karp +
, http://fr.dbpedia.org/resource/Couplage_%28th%C3%A9orie_des_graphes%29 +
, http://fr.dbpedia.org/resource/Int%C3%A9gration_%C3%A0_tr%C3%A8s_grande_%C3%A9chelle +
, http://fr.dbpedia.org/resource/Optimisation_combinatoire +
, http://fr.dbpedia.org/resource/Optimisation_SDP +
, http://fr.dbpedia.org/resource/Probl%C3%A8me_de_d%C3%A9cision +
|
| http://fr.dbpedia.org/property/année
|
2003
, 2000
, 2007
, 2005
, 2008
, 2013
, 1995
|
| http://fr.dbpedia.org/property/auteur
|
http://fr.dbpedia.org/resource/Gerhard_Woeginger +
, http://fr.dbpedia.org/resource/Marek_Karpinski +
, http://fr.dbpedia.org/resource/Subhash_Khot +
, Magnús Halldórsson
, Viggo Kann
, Pierre Pansu
, Pierluigi Crescenzi
|
| http://fr.dbpedia.org/property/consultéLe
|
"2014-06-23"^^xsd:date
|
| http://fr.dbpedia.org/property/date
|
"2011-11-10"^^xsd:date
|
| http://fr.dbpedia.org/property/doi
|
10.1007
, 10.1137
, 10.1145
|
| http://fr.dbpedia.org/property/fr
|
méthode des probabilités conditionnelles
|
| http://fr.dbpedia.org/property/isbn
|
978
|
| http://fr.dbpedia.org/property/langue
|
en
|
| http://fr.dbpedia.org/property/lienAuteur
|
Michel Goemans
|
| http://fr.dbpedia.org/property/lireEnLigne
|
http://cermics.enpc.fr/~meuniefr/hermes13dec.pdf +
|
| http://fr.dbpedia.org/property/nom
|
Mitzenmacher
, Meunier
, Gambosi
, O'Donnell
, Newman
, Kann
, Kindler
, Ausiello
, Upfal
, Crescenzi
, Protasi
, Mossel
, Khuller
, Goemans
, Young
, Williamson
, Sebo
, Marchetti-Spaccamela
, Raghavachari
|
| http://fr.dbpedia.org/property/numéro
|
1
, 6
|
| http://fr.dbpedia.org/property/pages
|
1115
|
| http://fr.dbpedia.org/property/passage
|
319
|
| http://fr.dbpedia.org/property/prénom
|
Eli
, Pierluigi
, Samir
, Marco
, Balaji
, Michael
, Alberto
, Giorgio
, Michel X.
, Alantha
, Elchanan
, Andras
, Guy
, Viggo
, Ryan
, Frédéric
, David P.
, Neal E.
|
| http://fr.dbpedia.org/property/périodique
|
http://fr.dbpedia.org/resource/Journal_of_the_ACM +
, SIAM Journal on Computing
|
| http://fr.dbpedia.org/property/site
|
http://fr.dbpedia.org/resource/Images_des_math%C3%A9matiques +
, A compendium of NP optimization problems
|
| http://fr.dbpedia.org/property/titre
|
Maximum Cut
, Probability and Computing: Randomized Algorithms and Probabilistic Analysis
, Le découpage des graphes
, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
, Mathématiques, l'explosion continue
|
| http://fr.dbpedia.org/property/titreChapitre
|
Parcours et coupes
, Greedy methods
, Max cut
|
| http://fr.dbpedia.org/property/titreOuvrage
|
Handbook of Approximation Algorithms and Metaheuristics
, Encyclopedia of Algorithms
, Graphes et applications-vol. 2
|
| http://fr.dbpedia.org/property/trad
|
Method of conditional probabilities
|
| http://fr.dbpedia.org/property/url
|
http://images.math.cnrs.fr/Le-decoupage-des-graphes.html +
, http://www.nada.kth.se/~viggo/wwwcompendium/node85.html +
|
| http://fr.dbpedia.org/property/volume
|
37
, 42
|
| http://fr.dbpedia.org/property/wikiPageUsesTemplate
|
http://fr.dbpedia.org/resource/Mod%C3%A8le:Randomized_Algorithms_%28Motwani_et_Raghavan%29 +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Lien +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Lien_web +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Article +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:R%C3%A9f%C3%A9rences +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Portail +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:%2C +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Chapitre +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Traduction/R%C3%A9f%C3%A9rence +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Ouvrage +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Palette_21_probl%C3%A8mes_NP-complets_de_Karp +
|
| http://fr.dbpedia.org/property/éditeur
|
Springer
, Chapman
, FSMP, SFS, SMF, SMAI
, Cambridge
, JC Fournier
|
| http://purl.org/dc/terms/subject
|
http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Probl%C3%A8me_NP-complet +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Concept_en_th%C3%A9orie_des_graphes +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://fr.wikipedia.org/wiki/Coupe_maximum?oldid=185260106&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Max-cut.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://fr.wikipedia.org/wiki/Coupe_maximum +
|
| owl:sameAs |
http://de.dbpedia.org/resource/Maximaler_Schnitt +
, http://it.dbpedia.org/resource/Taglio_massimo +
, http://zh.dbpedia.org/resource/%E6%9C%80%E5%A4%A7%E5%89%B2%E5%95%8F%E9%A1%8C +
, http://g.co/kg/m/04n598f +
, http://ru.dbpedia.org/resource/%D0%9C%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D0%B7_%D0%B3%D1%80%D0%B0%D1%84%D0%B0 +
, http://fa.dbpedia.org/resource/%D8%A8%D8%B1%D8%B4_%D8%A8%DB%8C%D8%B4%DB%8C%D9%86%D9%87 +
, http://dbpedia.org/resource/Maximum_cut +
, http://fr.dbpedia.org/resource/Coupe_maximum +
, http://www.wikidata.org/entity/Q942557 +
, http://nl.dbpedia.org/resource/Maximale_snede +
, http://ma-graph.org/entity/165526019 +
, http://pt.dbpedia.org/resource/Corte_M%C3%A1ximo +
, http://sr.dbpedia.org/resource/Maksimalno_odsecanje +
|
| rdfs:comment |
En théorie des graphes et en algorithmique … 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.mment dans le contexte de l'approximation.
|
| rdfs:label |
Максимальный разрез графа
, Coupe maximum
|
