{ "http://fr.dbpedia.org/resource/Coupe_maximum" : { "http://www.w3.org/2000/01/rdf-schema#label" : [ { "type" : "literal", "value" : "\u041C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u044B\u0439 \u0440\u0430\u0437\u0440\u0435\u0437 \u0433\u0440\u0430\u0444\u0430" , "lang" : "ru" } , { "type" : "literal", "value" : "Coupe maximum" , "lang" : "fr" } ] , "http://www.w3.org/2000/01/rdf-schema#comment" : [ { "type" : "literal", "value" : "En th\u00E9orie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'ar\u00EAtes que n'importe quelle autre coupe. Une extension de la d\u00E9finition consiste \u00E0 consid\u00E9rer des poids associ\u00E9s aux ar\u00EAtes. On consid\u00E8re alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique th\u00E9orique et en \u00E9lectronique. Mais elles sont surtout connues pour le probl\u00E8me algorithmique qui consiste \u00E0 trouver une coupe maximum, appel\u00E9 couramment MAX-CUT, un probl\u00E8me relativement bien \u00E9tudi\u00E9, notamment dans le contexte de l'approximation." , "lang" : "fr" } ] , "http://www.w3.org/2002/07/owl#sameAs" : [ { "type" : "uri", "value" : "http://de.dbpedia.org/resource/Maximaler_Schnitt" } , { "type" : "uri", "value" : "http://it.dbpedia.org/resource/Taglio_massimo" } , { "type" : "uri", "value" : "http://zh.dbpedia.org/resource/\u6700\u5927\u5272\u554F\u984C" } , { "type" : "uri", "value" : "http://g.co/kg/m/04n598f" } , { "type" : "uri", "value" : "http://ru.dbpedia.org/resource/\u041C\u0430\u043A\u0441\u0438\u043C\u0430\u043B\u044C\u043D\u044B\u0439_\u0440\u0430\u0437\u0440\u0435\u0437_\u0433\u0440\u0430\u0444\u0430" } , { "type" : "uri", "value" : "http://fa.dbpedia.org/resource/\u0628\u0631\u0634_\u0628\u06CC\u0634\u06CC\u0646\u0647" } , { "type" : "uri", "value" : "http://dbpedia.org/resource/Maximum_cut" } , { "type" : "uri", "value" : "http://www.wikidata.org/entity/Q942557" } , { "type" : "uri", "value" : "http://nl.dbpedia.org/resource/Maximale_snede" } , { "type" : "uri", "value" : "http://ma-graph.org/entity/165526019" } , { "type" : "uri", "value" : "http://pt.dbpedia.org/resource/Corte_M\u00E1ximo" } , { "type" : "uri", "value" : "http://sr.dbpedia.org/resource/Maksimalno_odsecanje" } ] , "http://dbpedia.org/ontology/wikiPageID" : [ { "type" : "literal", "value" : 7755716 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://dbpedia.org/ontology/wikiPageRevisionID" : [ { "type" : "literal", "value" : 185260106 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://dbpedia.org/ontology/wikiPageWikiLink" : [ { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Th\u00E9orie_de_l'ordonnancement" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Luca_Trevisan" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Cat\u00E9gorie:Probl\u00E8me_NP-complet" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Coupe_(th\u00E9orie_des_graphes)" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Physique_th\u00E9orique" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Physique_statistique" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Gerhard_Woeginger" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Sch\u00E9ma_d'approximation_en_temps_polynomial" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Algorithme_de_fouille_de_flots_de_donn\u00E9es" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le_d'Ising" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Cat\u00E9gorie:Concept_en_th\u00E9orie_des_graphes" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Probl\u00E8me_de_satisfaction_de_contraintes" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/R\u00E9duction_(complexit\u00E9)" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Michel_Goemans" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Th\u00E9or\u00E8me_flot-max/coupe-min" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Graphe_cordal" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Fichier:Max-cut.svg" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Algorithme_probabiliste" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Algorithmique" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Probl\u00E8me_du_sac_\u00E0_dos" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/APX_(complexit\u00E9)" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/S\u00E9quen\u00E7age_de_t\u00E2ches" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/M\u00E9thode_des_poids_multiplicatifs" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Images_des_math\u00E9matiques" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Journal_of_the_ACM" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/P_(complexit\u00E9)" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Th\u00E9orie_spectrale_des_graphes" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/D\u00E9randomisation" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Conjecture_des_jeux_uniques" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Subhash_Khot" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Coupe_minimum" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Th\u00E9orie_des_graphes" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Probl\u00E8me_P_\u225F_NP" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Marek_Karpinski" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Probl\u00E8me_NP-complet" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Algorithme_d'approximation" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Algorithme_d'Edmonds_pour_les_couplages" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Densit\u00E9_d'un_graphe" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Graphe_planaire" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Spin" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Graphe_scind\u00E9" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/21_probl\u00E8mes_NP-complets_de_Karp" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Couplage_(th\u00E9orie_des_graphes)" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Int\u00E9gration_\u00E0_tr\u00E8s_grande_\u00E9chelle" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Optimisation_combinatoire" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Optimisation_SDP" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Probl\u00E8me_de_d\u00E9cision" } ] , "http://dbpedia.org/ontology/wikiPageExternalLink" : [ { "type" : "uri", "value" : "http://www.liafa.jussieu.fr/~nschaban/publications/2012/2012-Maths-PansuSchabanel.pdf" } , { "type" : "uri", "value" : "http://cermics.enpc.fr/~meuniefr/hermes13dec.pdf" } , { "type" : "uri", "value" : "http://images.math.cnrs.fr/Le-decoupage-des-graphes.html" } , { "type" : "uri", "value" : "http://www.nada.kth.se/~viggo/wwwcompendium/node85.html" } , { "type" : "uri", "value" : "http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/" } ] , "http://dbpedia.org/ontology/wikiPageLength" : [ { "type" : "literal", "value" : "17302" , "datatype" : "http://www.w3.org/2001/XMLSchema#nonNegativeInteger" } ] , "http://purl.org/dc/terms/subject" : [ { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Cat\u00E9gorie:Probl\u00E8me_NP-complet" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Cat\u00E9gorie:Concept_en_th\u00E9orie_des_graphes" } ] , "http://fr.dbpedia.org/property/wikiPageUsesTemplate" : [ { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Randomized_Algorithms_(Motwani_et_Raghavan)" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Lien" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Lien_web" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Article" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:R\u00E9f\u00E9rences" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Portail" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:," } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Chapitre" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Traduction/R\u00E9f\u00E9rence" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Ouvrage" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Mod\u00E8le:Palette_21_probl\u00E8mes_NP-complets_de_Karp" } ] , "http://www.w3.org/ns/prov#wasDerivedFrom" : [ { "type" : "uri", "value" : "http://fr.wikipedia.org/wiki/Coupe_maximum?oldid=185260106&ns=0" } ] , "http://xmlns.com/foaf/0.1/depiction" : [ { "type" : "uri", "value" : "http://commons.wikimedia.org/wiki/Special:FilePath/Max-cut.svg" } ] , "http://fr.dbpedia.org/property/ann\u00E9e" : [ { "type" : "literal", "value" : 2003 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 2000 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 2007 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 2005 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 2008 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 2013 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 1995 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://fr.dbpedia.org/property/auteur" : [ { "type" : "literal", "value" : "Magn\u00FAs Halld\u00F3rsson" , "lang" : "fr" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Gerhard_Woeginger" } , { "type" : "literal", "value" : "Viggo Kann" , "lang" : "fr" } , { "type" : "literal", "value" : "Pierre Pansu" , "lang" : "fr" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Marek_Karpinski" } , { "type" : "literal", "value" : "Pierluigi Crescenzi" , "lang" : "fr" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Subhash_Khot" } ] , "http://fr.dbpedia.org/property/consult\u00E9Le" : [ { "type" : "literal", "value" : "2014-06-23" , "datatype" : "http://www.w3.org/2001/XMLSchema#date" } ] , "http://fr.dbpedia.org/property/date" : [ { "type" : "literal", "value" : "2011-11-10" , "datatype" : "http://www.w3.org/2001/XMLSchema#date" } ] , "http://fr.dbpedia.org/property/doi" : [ { "type" : "literal", "value" : 10.1007 , "datatype" : "http://www.w3.org/2001/XMLSchema#double" } , { "type" : "literal", "value" : 10.1137 , "datatype" : "http://www.w3.org/2001/XMLSchema#double" } , { "type" : "literal", "value" : 10.1145 , "datatype" : "http://www.w3.org/2001/XMLSchema#double" } ] , "http://fr.dbpedia.org/property/fr" : [ { "type" : "literal", "value" : "m\u00E9thode des probabilit\u00E9s conditionnelles" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/isbn" : [ { "type" : "literal", "value" : 978 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://fr.dbpedia.org/property/langue" : [ { "type" : "literal", "value" : "en" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/lienAuteur" : [ { "type" : "literal", "value" : "Michel Goemans" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/lireEnLigne" : [ { "type" : "uri", "value" : "http://cermics.enpc.fr/~meuniefr/hermes13dec.pdf" } ] , "http://fr.dbpedia.org/property/nom" : [ { "type" : "literal", "value" : "Mitzenmacher" , "lang" : "fr" } , { "type" : "literal", "value" : "Meunier" , "lang" : "fr" } , { "type" : "literal", "value" : "Gambosi" , "lang" : "fr" } , { "type" : "literal", "value" : "O'Donnell" , "lang" : "fr" } , { "type" : "literal", "value" : "Newman" , "lang" : "fr" } , { "type" : "literal", "value" : "Kann" , "lang" : "fr" } , { "type" : "literal", "value" : "Kindler" , "lang" : "fr" } , { "type" : "literal", "value" : "Ausiello" , "lang" : "fr" } , { "type" : "literal", "value" : "Upfal" , "lang" : "fr" } , { "type" : "literal", "value" : "Crescenzi" , "lang" : "fr" } , { "type" : "literal", "value" : "Protasi" , "lang" : "fr" } , { "type" : "literal", "value" : "Mossel" , "lang" : "fr" } , { "type" : "literal", "value" : "Khuller" , "lang" : "fr" } , { "type" : "literal", "value" : "Goemans" , "lang" : "fr" } , { "type" : "literal", "value" : "Young" , "lang" : "fr" } , { "type" : "literal", "value" : "Williamson" , "lang" : "fr" } , { "type" : "literal", "value" : "Sebo" , "lang" : "fr" } , { "type" : "literal", "value" : "Marchetti-Spaccamela" , "lang" : "fr" } , { "type" : "literal", "value" : "Raghavachari" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/num\u00E9ro" : [ { "type" : "literal", "value" : 1 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 6 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://fr.dbpedia.org/property/pages" : [ { "type" : "literal", "value" : 1115 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://fr.dbpedia.org/property/passage" : [ { "type" : "literal", "value" : 319 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://fr.dbpedia.org/property/pr\u00E9nom" : [ { "type" : "literal", "value" : "Eli" , "lang" : "fr" } , { "type" : "literal", "value" : "Pierluigi" , "lang" : "fr" } , { "type" : "literal", "value" : "Samir" , "lang" : "fr" } , { "type" : "literal", "value" : "Marco" , "lang" : "fr" } , { "type" : "literal", "value" : "Balaji" , "lang" : "fr" } , { "type" : "literal", "value" : "Michael" , "lang" : "fr" } , { "type" : "literal", "value" : "Alberto" , "lang" : "fr" } , { "type" : "literal", "value" : "Giorgio" , "lang" : "fr" } , { "type" : "literal", "value" : "Michel X." , "lang" : "fr" } , { "type" : "literal", "value" : "Alantha" , "lang" : "fr" } , { "type" : "literal", "value" : "Elchanan" , "lang" : "fr" } , { "type" : "literal", "value" : "Andras" , "lang" : "fr" } , { "type" : "literal", "value" : "Guy" , "lang" : "fr" } , { "type" : "literal", "value" : "Viggo" , "lang" : "fr" } , { "type" : "literal", "value" : "Ryan" , "lang" : "fr" } , { "type" : "literal", "value" : "Fr\u00E9d\u00E9ric" , "lang" : "fr" } , { "type" : "literal", "value" : "David P." , "lang" : "fr" } , { "type" : "literal", "value" : "Neal E." , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/p\u00E9riodique" : [ { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Journal_of_the_ACM" } , { "type" : "literal", "value" : "SIAM Journal on Computing" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/site" : [ { "type" : "literal", "value" : "A compendium of NP optimization problems" , "lang" : "fr" } , { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/Images_des_math\u00E9matiques" } ] , "http://fr.dbpedia.org/property/titre" : [ { "type" : "literal", "value" : "Maximum Cut" , "lang" : "fr" } , { "type" : "literal", "value" : "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" , "lang" : "fr" } , { "type" : "literal", "value" : "Le d\u00E9coupage des graphes" , "lang" : "fr" } , { "type" : "literal", "value" : "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming" , "lang" : "fr" } , { "type" : "literal", "value" : "Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?" , "lang" : "fr" } , { "type" : "literal", "value" : "Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties" , "lang" : "fr" } , { "type" : "literal", "value" : "Math\u00E9matiques, l'explosion continue" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/titreChapitre" : [ { "type" : "literal", "value" : "Parcours et coupes" , "lang" : "fr" } , { "type" : "literal", "value" : "Greedy methods" , "lang" : "fr" } , { "type" : "literal", "value" : "Max cut" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/titreOuvrage" : [ { "type" : "literal", "value" : "Handbook of Approximation Algorithms and Metaheuristics" , "lang" : "fr" } , { "type" : "literal", "value" : "Encyclopedia of Algorithms" , "lang" : "fr" } , { "type" : "literal", "value" : "Graphes et applications-vol. 2" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/trad" : [ { "type" : "literal", "value" : "Method of conditional probabilities" , "lang" : "fr" } ] , "http://fr.dbpedia.org/property/url" : [ { "type" : "uri", "value" : "http://images.math.cnrs.fr/Le-decoupage-des-graphes.html" } , { "type" : "uri", "value" : "http://www.nada.kth.se/~viggo/wwwcompendium/node85.html" } ] , "http://fr.dbpedia.org/property/volume" : [ { "type" : "literal", "value" : 37 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } , { "type" : "literal", "value" : 42 , "datatype" : "http://www.w3.org/2001/XMLSchema#integer" } ] , "http://fr.dbpedia.org/property/\u00E9diteur" : [ { "type" : "literal", "value" : "Springer" , "lang" : "fr" } , { "type" : "literal", "value" : "Chapman" , "lang" : "fr" } , { "type" : "literal", "value" : "FSMP, SFS, SMF, SMAI" , "lang" : "fr" } , { "type" : "literal", "value" : "Cambridge" , "lang" : "fr" } , { "type" : "literal", "value" : "JC Fournier" , "lang" : "fr" } ] , "http://dbpedia.org/ontology/thumbnail" : [ { "type" : "uri", "value" : "http://commons.wikimedia.org/wiki/Special:FilePath/Max-cut.svg?width=300" } ] , "http://xmlns.com/foaf/0.1/isPrimaryTopicOf" : [ { "type" : "uri", "value" : "http://fr.wikipedia.org/wiki/Coupe_maximum" } ] , "http://dbpedia.org/ontology/abstract" : [ { "type" : "literal", "value" : "En th\u00E9orie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'ar\u00EAtes que n'importe quelle autre coupe. Une extension de la d\u00E9finition consiste \u00E0 consid\u00E9rer des poids associ\u00E9s aux ar\u00EAtes. On consid\u00E8re alors la coupe ayant le poids total maximum. Les coupes maximums sont des objets utiles notamment en physique th\u00E9orique et en \u00E9lectronique. Mais elles sont surtout connues pour le probl\u00E8me algorithmique qui consiste \u00E0 trouver une coupe maximum, appel\u00E9 couramment MAX-CUT, un probl\u00E8me relativement bien \u00E9tudi\u00E9, notamment dans le contexte de l'approximation." , "lang" : "fr" } ] , "http://dbpedia.org/ontology/isPartOf" : [ { "type" : "uri", "value" : "http://fr.dbpedia.org/resource/21_probl\u00E8mes_NP-complets_de_Karp" } ] } }