This HTML5 document contains 181 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dcthttp://purl.org/dc/terms/
n18http://images.math.cnrs.fr/
n19http://fr.dbpedia.org/resource/Théorème_flot-max/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n23http://g.co/kg/m/
dbpedia-ruhttp://ru.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-srhttp://sr.dbpedia.org/resource/
category-frhttp://fr.dbpedia.org/resource/Catégorie:
n29http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/
dbpedia-pthttp://pt.dbpedia.org/resource/
n5http://www.liafa.jussieu.fr/~nschaban/publications/2012/
n6http://fr.dbpedia.org/resource/Modèle:
n7http://cermics.enpc.fr/~meuniefr/
n21http://fr.dbpedia.org/resource/Fichier:
wikipedia-frhttp://fr.wikipedia.org/wiki/
n16http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-fahttp://fa.dbpedia.org/resource/
n27http://fr.dbpedia.org/resource/Modèle:Traduction/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n22http://www.nada.kth.se/~viggo/wwwcompendium/
owlhttp://www.w3.org/2002/07/owl#
n31http://ma-graph.org/entity/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-frhttp://fr.dbpedia.org/resource/
prop-frhttp://fr.dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbpedia-nlhttp://nl.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbpedia-fr:Coupe_maximum
rdfs:label
Максимальный разрез графа Coupe maximum
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.
owl:sameAs
dbpedia-de:Maximaler_Schnitt dbpedia-it:Taglio_massimo dbpedia-zh:最大割問題 n23:04n598f dbpedia-ru:Максимальный_разрез_графа dbpedia-fa:برش_بیشینه dbr:Maximum_cut wikidata:Q942557 dbpedia-nl:Maximale_snede n31:165526019 dbpedia-pt:Corte_Máximo dbpedia-sr:Maksimalno_odsecanje
dbo:wikiPageID
7755716
dbo:wikiPageRevisionID
185260106
dbo:wikiPageWikiLink
dbpedia-fr:Théorie_de_l'ordonnancement dbpedia-fr:Luca_Trevisan category-fr:Problème_NP-complet dbpedia-fr:Coupe_(théorie_des_graphes) dbpedia-fr:Physique_théorique dbpedia-fr:Physique_statistique dbpedia-fr:Gerhard_Woeginger dbpedia-fr:Schéma_d'approximation_en_temps_polynomial dbpedia-fr:Algorithme_de_fouille_de_flots_de_données dbpedia-fr:Modèle_d'Ising category-fr:Concept_en_théorie_des_graphes dbpedia-fr:Problème_de_satisfaction_de_contraintes dbpedia-fr:Réduction_(complexité) dbpedia-fr:Michel_Goemans n19:coupe-min dbpedia-fr:Graphe_cordal n21:Max-cut.svg dbpedia-fr:Algorithme_probabiliste dbpedia-fr:Algorithmique dbpedia-fr:Problème_du_sac_à_dos dbpedia-fr:APX_(complexité) dbpedia-fr:Séquençage_de_tâches dbpedia-fr:Méthode_des_poids_multiplicatifs dbpedia-fr:Images_des_mathématiques dbpedia-fr:Journal_of_the_ACM dbpedia-fr:P_(complexité) dbpedia-fr:Théorie_spectrale_des_graphes dbpedia-fr:Dérandomisation dbpedia-fr:Conjecture_des_jeux_uniques dbpedia-fr:Subhash_Khot dbpedia-fr:Coupe_minimum dbpedia-fr:Théorie_des_graphes dbpedia-fr:Problème_P_≟_NP dbpedia-fr:Marek_Karpinski dbpedia-fr:Problème_NP-complet dbpedia-fr:Algorithme_d'approximation dbpedia-fr:Algorithme_d'Edmonds_pour_les_couplages dbpedia-fr:Densité_d'un_graphe dbpedia-fr:Graphe_planaire dbpedia-fr:Spin dbpedia-fr:Graphe_scindé dbpedia-fr:21_problèmes_NP-complets_de_Karp dbpedia-fr:Couplage_(théorie_des_graphes) dbpedia-fr:Intégration_à_très_grande_échelle dbpedia-fr:Optimisation_combinatoire dbpedia-fr:Optimisation_SDP dbpedia-fr:Problème_de_décision
dbo:wikiPageExternalLink
n5:2012-Maths-PansuSchabanel.pdf n7:hermes13dec.pdf n18:Le-decoupage-des-graphes.html n22:node85.html n29:
dbo:wikiPageLength
17302
dct:subject
category-fr:Problème_NP-complet category-fr:Concept_en_théorie_des_graphes
prop-fr:wikiPageUsesTemplate
n6:Randomized_Algorithms_(Motwani_et_Raghavan) n6:Lien n6:Lien_web n6:Article n6:Références n6:Portail n6:, n6:Chapitre n27:Référence n6:Ouvrage n6:Palette_21_problèmes_NP-complets_de_Karp
prov:wasDerivedFrom
wikipedia-fr:Coupe_maximum?oldid=185260106&ns=0
foaf:depiction
n16:Max-cut.svg
prop-fr:année
2003 2000 2007 2005 2008 2013 1995
prop-fr:auteur
Magnús Halldórsson dbpedia-fr:Gerhard_Woeginger Viggo Kann Pierre Pansu dbpedia-fr:Marek_Karpinski Pierluigi Crescenzi dbpedia-fr:Subhash_Khot
prop-fr:consultéLe
2014-06-23
prop-fr:date
2011-11-10
prop-fr:doi
10.1007 10.1137 10.1145
prop-fr:fr
méthode des probabilités conditionnelles
prop-fr:isbn
978
prop-fr:langue
en
prop-fr:lienAuteur
Michel Goemans
prop-fr:lireEnLigne
n7:hermes13dec.pdf
prop-fr:nom
Mitzenmacher Meunier Gambosi O'Donnell Newman Kann Kindler Ausiello Upfal Crescenzi Protasi Mossel Khuller Goemans Young Williamson Sebo Marchetti-Spaccamela Raghavachari
prop-fr:numéro
1 6
prop-fr:pages
1115
prop-fr:passage
319
prop-fr: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.
prop-fr:périodique
dbpedia-fr:Journal_of_the_ACM SIAM Journal on Computing
prop-fr:site
A compendium of NP optimization problems dbpedia-fr:Images_des_mathématiques
prop-fr: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
prop-fr:titreChapitre
Parcours et coupes Greedy methods Max cut
prop-fr:titreOuvrage
Handbook of Approximation Algorithms and Metaheuristics Encyclopedia of Algorithms Graphes et applications-vol. 2
prop-fr:trad
Method of conditional probabilities
prop-fr:url
n18:Le-decoupage-des-graphes.html n22:node85.html
prop-fr:volume
37 42
prop-fr:éditeur
Springer Chapman FSMP, SFS, SMF, SMAI Cambridge JC Fournier
dbo:thumbnail
n16:Max-cut.svg?width=300
foaf:isPrimaryTopicOf
wikipedia-fr:Coupe_maximum
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.
dbo:isPartOf
dbpedia-fr:21_problèmes_NP-complets_de_Karp