| Property |
Value |
| dbo:abstract
|
- En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets d'un graphe tous adjacents les uns aux autres, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées. Les formulations courantes du problème de la clique incluent la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets), la recherche d'une clique de poids maximal dans un graphe pondéré, la liste de toutes les cliques maximums et la résolution du problème de décision consistant à déterminer si un graphe contient une clique plus grande qu'une taille donnée. Le problème de la clique apparaît dans la situation réelle suivante. Considérons un réseau social, où les sommets du graphe représentent des personnes et les arêtes représentent la connaissance mutuelle entre les personnes. Une clique représente alors un sous-ensemble de personnes qui se connaissent toutes mutuellement, et des algorithmes pour trouver des cliques peuvent être utilisés pour découvrir ces groupes d'amis communs. Outre ses applications aux réseaux sociaux, le problème de la clique a également de nombreuses applications en bioinformatique et en chimie numérique. La plupart des versions du problème de la clique sont des problèmes difficiles. Le problème décisionnel de la clique est NP-complet (l'un des 21 problèmes NP-complets de Karp). Le problème de trouver une k-clique est à la fois intraitable à paramètre fixé (il n'est pas dans la classe de problèmes FPT) et est (en). Lister toutes les cliques maximums peut nécessiter un temps exponentiel car il existe des graphes avec un nombre de cliques maximums exponentiel en le nombre de sommets. Par conséquent, une grande partie de la théorie sur le problème de la clique est consacrée à l'identification de types particuliers de graphes qui admettent des algorithmes plus efficaces, ou à l'établissement de la difficulté algorithmique du problème général dans divers modèles de calcul. Pour trouver une clique maximum, on peut inspecter tous les sous-ensembles du graphe, mais ce type de recherche exhaustive est trop long pour être utilisable dans des graphes comprenant plus de quelques dizaines de sommets. Bien qu'aucun algorithme de temps polynomial ne soit connu pour ce problème, des algorithmes plus efficaces que la recherche exhaustive sont connus. Par exemple, l'algorithme de Bron-Kerbosch peut être utilisé pour lister toutes les cliques maximums, en temps optimal dans le pire cas, et il est également possible de les lister en temps polynomial par clique. (fr)
- En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets d'un graphe tous adjacents les uns aux autres, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées. Les formulations courantes du problème de la clique incluent la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets), la recherche d'une clique de poids maximal dans un graphe pondéré, la liste de toutes les cliques maximums et la résolution du problème de décision consistant à déterminer si un graphe contient une clique plus grande qu'une taille donnée. Le problème de la clique apparaît dans la situation réelle suivante. Considérons un réseau social, où les sommets du graphe représentent des personnes et les arêtes représentent la connaissance mutuelle entre les personnes. Une clique représente alors un sous-ensemble de personnes qui se connaissent toutes mutuellement, et des algorithmes pour trouver des cliques peuvent être utilisés pour découvrir ces groupes d'amis communs. Outre ses applications aux réseaux sociaux, le problème de la clique a également de nombreuses applications en bioinformatique et en chimie numérique. La plupart des versions du problème de la clique sont des problèmes difficiles. Le problème décisionnel de la clique est NP-complet (l'un des 21 problèmes NP-complets de Karp). Le problème de trouver une k-clique est à la fois intraitable à paramètre fixé (il n'est pas dans la classe de problèmes FPT) et est (en). Lister toutes les cliques maximums peut nécessiter un temps exponentiel car il existe des graphes avec un nombre de cliques maximums exponentiel en le nombre de sommets. Par conséquent, une grande partie de la théorie sur le problème de la clique est consacrée à l'identification de types particuliers de graphes qui admettent des algorithmes plus efficaces, ou à l'établissement de la difficulté algorithmique du problème général dans divers modèles de calcul. Pour trouver une clique maximum, on peut inspecter tous les sous-ensembles du graphe, mais ce type de recherche exhaustive est trop long pour être utilisable dans des graphes comprenant plus de quelques dizaines de sommets. Bien qu'aucun algorithme de temps polynomial ne soit connu pour ce problème, des algorithmes plus efficaces que la recherche exhaustive sont connus. Par exemple, l'algorithme de Bron-Kerbosch peut être utilisé pour lister toutes les cliques maximums, en temps optimal dans le pire cas, et il est également possible de les lister en temps polynomial par clique. (fr)
|
| dbo:isPartOf
| |
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 82102 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:accèsDoi
| |
| prop-fr:accèsHdl
| |
| prop-fr:année
|
- 1935 (xsd:integer)
- 1949 (xsd:integer)
- 1957 (xsd:integer)
- 1965 (xsd:integer)
- 1971 (xsd:integer)
- 1972 (xsd:integer)
- 1973 (xsd:integer)
- 1976 (xsd:integer)
- 1977 (xsd:integer)
- 1978 (xsd:integer)
- 1979 (xsd:integer)
- 1980 (xsd:integer)
- 1981 (xsd:integer)
- 1983 (xsd:integer)
- 1985 (xsd:integer)
- 1986 (xsd:integer)
- 1987 (xsd:integer)
- 1988 (xsd:integer)
- 1990 (xsd:integer)
- 1991 (xsd:integer)
- 1992 (xsd:integer)
- 1993 (xsd:integer)
- 1994 (xsd:integer)
- 1995 (xsd:integer)
- 1996 (xsd:integer)
- 1997 (xsd:integer)
- 1998 (xsd:integer)
- 1999 (xsd:integer)
- 2000 (xsd:integer)
- 2001 (xsd:integer)
- 2002 (xsd:integer)
- 2003 (xsd:integer)
- 2004 (xsd:integer)
- 2005 (xsd:integer)
- 2006 (xsd:integer)
- 2007 (xsd:integer)
- 2008 (xsd:integer)
- 2009 (xsd:integer)
- 2013 (xsd:integer)
- 2015 (xsd:integer)
|
| prop-fr:arxiv
|
- 1103.031800 (xsd:double)
- 1503.064470 (xsd:double)
- math/9210222 (fr)
- quant-ph/0012104 (fr)
- quant-ph/0310134 (fr)
- quant-ph/0311038 (fr)
|
| prop-fr:auteur
|
- David S. Johnson (fr)
- Michael R. Garey (fr)
- National Research Council Committee on Mathematical Challenges from Computational Chemistry (fr)
- David S. Johnson (fr)
- Michael R. Garey (fr)
- National Research Council Committee on Mathematical Challenges from Computational Chemistry (fr)
|
| prop-fr:bibcode
|
- 1997 (xsd:integer)
- 2000 (xsd:integer)
- 2003 (xsd:integer)
|
| prop-fr:chapter
|
- Exponential lower bounds for restricted monotone circuits (fr)
- Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring (fr)
- Simple and fast: Improving a branch-and-bound algorithm for maximum clique (fr)
- Approximating clique is almost NP-complete (fr)
- Finding, minimizing, and counting weighted subgraphs (fr)
- An efficient branch-and-bound algorithm for finding a maximum clique (fr)
- Linear degree extractors and the inapproximability of max clique and chromatic number (fr)
- Exponential lower bounds for restricted monotone circuits (fr)
- Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring (fr)
- Simple and fast: Improving a branch-and-bound algorithm for maximum clique (fr)
- Approximating clique is almost NP-complete (fr)
- Finding, minimizing, and counting weighted subgraphs (fr)
- An efficient branch-and-bound algorithm for finding a maximum clique (fr)
- Linear degree extractors and the inapproximability of max clique and chromatic number (fr)
|
| prop-fr:chapterUrl
| |
| prop-fr:citeseerx
| |
| prop-fr:consultéLe
| |
| prop-fr:contenu
|
- Pour réduire le problème 3-SAT vers celui de la clique, à chaque formule 3-CNF, on associe un graphe non orienté dont le nombre de sommets est trois fois le nombre de clauses de la manière suivante :
* à chacun des trois littéraux de chaque clause, on associe un sommet ;
* on relie les sommets par des arêtes de la manière suivante : deux sommets qui sont associés aux littéraux d'une même clause ne sont pas reliés par une arête, deux sommets qui sont associés à un littéral et sa négation ne sont pas reliés non plus, tous les autres couples de sommets sont reliés.
On démontre alors que la formule à clauses est satisfiable si et seulement si le graphe a une clique d'ordre .
Idée de la preuve :
Si la formule est satisfiable, il existe une assignation des variables pour laquelle la valeur d'au moins un littéral de chaque clause est VRAI. L'ensemble formé des sommets associés à l'un de ces littéraux par clause est une clique du graphe.
Si le graphe a une clique d'ordre , elle contient exactement un sommet parmi les trois qui représentent les littéraux de chaque clause ; on peut définir une assignation des variables pour laquelle la valeur de ces littéraux est VRAI ; la valeur de la formule pour cette assignation est alors VRAI. (fr)
- Pour réduire le problème 3-SAT vers celui de la clique, à chaque formule 3-CNF, on associe un graphe non orienté dont le nombre de sommets est trois fois le nombre de clauses de la manière suivante :
* à chacun des trois littéraux de chaque clause, on associe un sommet ;
* on relie les sommets par des arêtes de la manière suivante : deux sommets qui sont associés aux littéraux d'une même clause ne sont pas reliés par une arête, deux sommets qui sont associés à un littéral et sa négation ne sont pas reliés non plus, tous les autres couples de sommets sont reliés.
On démontre alors que la formule à clauses est satisfiable si et seulement si le graphe a une clique d'ordre .
Idée de la preuve :
Si la formule est satisfiable, il existe une assignation des variables pour laquelle la valeur d'au moins un littéral de chaque clause est VRAI. L'ensemble formé des sommets associés à l'un de ces littéraux par clause est une clique du graphe.
Si le graphe a une clique d'ordre , elle contient exactement un sommet parmi les trois qui représentent les littéraux de chaque clause ; on peut définir une assignation des variables pour laquelle la valeur de ces littéraux est VRAI ; la valeur de la formule pour cette assignation est alors VRAI. (fr)
|
| prop-fr:contribution
|
- 5.300000 (xsd:double)
- 9.400000 (xsd:double)
- 34.500000 (xsd:double)
- Finding and counting given length cycles (fr)
- Probabilistic analysis of some combinatorial search problems (fr)
- An introduction to chordal graphs and clique trees (fr)
- Heuristics for maximum clique and independent set (fr)
- Test set compaction algorithms for combinational circuits (fr)
- New algorithms for enumerating all maximal cliques (fr)
- On maximum clique problems in very large graphs (fr)
- Reducibility among combinatorial problems (fr)
- Sum-of-squares lower bounds for planted clique (fr)
- The complexity of theorem-proving procedures (fr)
- The maximum clique problem (fr)
- Towards maximum independent sets on massive graphs (fr)
- Using constraint programming to solve the maximum clique problem (fr)
|
| prop-fr:contributionUrl
| |
| prop-fr:date
|
- June 26, 1990 (fr)
- June 26, 1990 (fr)
|
| prop-fr:doi
|
- 10.100200 (xsd:double)
- 10.100600 (xsd:double)
- 10.100700 (xsd:double)
- 10.101600 (xsd:double)
- 10.102100 (xsd:double)
- 10.102300 (xsd:double)
- 10.107300 (xsd:double)
- 10.108000 (xsd:double)
- 10.109000 (xsd:double)
- 10.110900 (xsd:double)
- 10.112600 (xsd:double)
- 10.113700 (xsd:double)
- 10.114500 (xsd:double)
- 10.147780 (xsd:double)
- 10.172260 (xsd:double)
- 10.230700 (xsd:double)
- 10.264210 (xsd:double)
- 10.715500 (xsd:double)
|
| prop-fr:déroulante
| |
| prop-fr:edition
| |
| prop-fr:editor1First
|
- J. (fr)
- J. L. (fr)
- R. E. (fr)
- D. S. (fr)
- J. (fr)
- J. L. (fr)
- R. E. (fr)
- D. S. (fr)
|
| prop-fr:editor1Last
|
- Miller (fr)
- Johnson (fr)
- Gross (fr)
- Abello (fr)
- Miller (fr)
- Johnson (fr)
- Gross (fr)
- Abello (fr)
|
| prop-fr:editor1Link
|
- David S. Johnson (fr)
- David S. Johnson (fr)
|
| prop-fr:editor2First
|
- J. (fr)
- M. A. (fr)
- J. W. (fr)
- J. (fr)
- M. A. (fr)
- J. W. (fr)
|
| prop-fr:editor2Last
|
- Thatcher (fr)
- Trick (fr)
- Yellen (fr)
- Vitter (fr)
- Thatcher (fr)
- Trick (fr)
- Yellen (fr)
- Vitter (fr)
|
| prop-fr:editor2Link
|
- Jeffrey Vitter (fr)
- Michael Trick (fr)
- Jeffrey Vitter (fr)
- Michael Trick (fr)
|
| prop-fr:editorFirst
| |
| prop-fr:editorLast
| |
| prop-fr:fr
|
- boxicité (fr)
- Dureté d'approximation (fr)
- graphe de dépendances (fr)
- boxicité (fr)
- Dureté d'approximation (fr)
- graphe de dépendances (fr)
|
| prop-fr:hdl
|
- 10.100700 (xsd:double)
- 10138 (xsd:integer)
|
| prop-fr:isbn
|
- 0 (xsd:integer)
- 1 (xsd:integer)
- 978 (xsd:integer)
- 9780471398455 (xsd:decimal)
|
| prop-fr:issn
|
- 18 (xsd:integer)
- 95 (xsd:integer)
|
| prop-fr:issue
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 3 (xsd:integer)
- 4 (xsd:integer)
- 5 (xsd:integer)
- 6 (xsd:integer)
- 7 (xsd:integer)
- 8 (xsd:integer)
- 9 (xsd:integer)
- 11 (xsd:integer)
- 13 (xsd:integer)
- 21 (xsd:integer)
- 395 (xsd:integer)
- 5337 (xsd:integer)
|
| prop-fr:journal
| |
| prop-fr:jstor
|
- 2289017 (xsd:integer)
- 2413432 (xsd:integer)
- 2785673 (xsd:integer)
|
| prop-fr:langue
|
- en (fr)
- ru (fr)
- en (fr)
- ru (fr)
|
| prop-fr:lienAuteur
|
- Abraham Lempel (fr)
- Béla Bollobás (fr)
- Paul Erdős (fr)
- Ryan Williams (fr)
- Alexander Razborov (fr)
- Avi Wigderson (fr)
- David Eppstein (fr)
- Leo Moser (fr)
- Rajeev Motwani (fr)
- Robert Tarjan (fr)
- Thomas H. Cormen (fr)
- Christos Papadimitriou (fr)
- George Szekeres (fr)
- Noga Alon (fr)
- Michael Sipser (fr)
- Sanjeev Arora (fr)
- Steven Skiena (fr)
- Carsten Lund (fr)
- Charles E. Leiserson (fr)
- Clifford Stein (fr)
- David S. Johnson (fr)
- László Lovász (fr)
- Takao Nishizeki (fr)
- Michael D. Plummer (fr)
- Larry Stockmeyer (fr)
- R. Duncan Luce (fr)
- Alexander Schrijver (fr)
- Amir Pnueli (fr)
- Johan Håstad (fr)
- Russell Impagliazzo (fr)
- Frank Harary (fr)
- Charles Colbourn (fr)
- Martin Charles Golumbic (fr)
- Jaroslav Nešetřil (fr)
- Michael Fellows (fr)
- Madhu Sudan (fr)
- Mario Szegedy (fr)
- Michael R. Garey (fr)
- Ron Rivest (fr)
- Shafi Goldwasser (fr)
- Shmuel Safra (fr)
- Stephen Cook (fr)
- Uriel Feige (fr)
- Peter Shor (fr)
- Uri Zwick (fr)
- Jeffrey Goldstone (fr)
- Jeffrey Lagarias (fr)
- Martin Grötschel (fr)
- Mihalis Yannakakis (fr)
- Richard J. Lipton (fr)
- Richard M. Karp (fr)
- Rod Burstall (fr)
- Shimon Even (fr)
- Stanley Wasserman (fr)
- Virginia Vassilevska Williams (fr)
- Abraham Lempel (fr)
- Béla Bollobás (fr)
- Paul Erdős (fr)
- Ryan Williams (fr)
- Alexander Razborov (fr)
- Avi Wigderson (fr)
- David Eppstein (fr)
- Leo Moser (fr)
- Rajeev Motwani (fr)
- Robert Tarjan (fr)
- Thomas H. Cormen (fr)
- Christos Papadimitriou (fr)
- George Szekeres (fr)
- Noga Alon (fr)
- Michael Sipser (fr)
- Sanjeev Arora (fr)
- Steven Skiena (fr)
- Carsten Lund (fr)
- Charles E. Leiserson (fr)
- Clifford Stein (fr)
- David S. Johnson (fr)
- László Lovász (fr)
- Takao Nishizeki (fr)
- Michael D. Plummer (fr)
- Larry Stockmeyer (fr)
- R. Duncan Luce (fr)
- Alexander Schrijver (fr)
- Amir Pnueli (fr)
- Johan Håstad (fr)
- Russell Impagliazzo (fr)
- Frank Harary (fr)
- Charles Colbourn (fr)
- Martin Charles Golumbic (fr)
- Jaroslav Nešetřil (fr)
- Michael Fellows (fr)
- Madhu Sudan (fr)
- Mario Szegedy (fr)
- Michael R. Garey (fr)
- Ron Rivest (fr)
- Shafi Goldwasser (fr)
- Shmuel Safra (fr)
- Stephen Cook (fr)
- Uriel Feige (fr)
- Peter Shor (fr)
- Uri Zwick (fr)
- Jeffrey Goldstone (fr)
- Jeffrey Lagarias (fr)
- Martin Grötschel (fr)
- Mihalis Yannakakis (fr)
- Richard J. Lipton (fr)
- Richard M. Karp (fr)
- Rod Burstall (fr)
- Shimon Even (fr)
- Stanley Wasserman (fr)
- Virginia Vassilevska Williams (fr)
|
| prop-fr:lienTitre
|
- Introduction to Algorithms (fr)
- Symposium on Foundations of Computer Science (fr)
- Introduction to the Theory of Computation (fr)
- Symposium on Theory of Computing (fr)
- European Symposium on Algorithms (fr)
- Introduction to Algorithms (fr)
- Symposium on Foundations of Computer Science (fr)
- Introduction to the Theory of Computation (fr)
- Symposium on Theory of Computing (fr)
- European Symposium on Algorithms (fr)
|
| prop-fr:lieu
|
- New York (fr)
- New York, NY, USA (fr)
- New York (fr)
- New York, NY, USA (fr)
|
| prop-fr:mr
|
- 110590 (xsd:integer)
- 182577 (xsd:integer)
- 411240 (xsd:integer)
- 651460 (xsd:integer)
- 837088 (xsd:integer)
- 860518 (xsd:integer)
- 1155280 (xsd:integer)
- 1254158 (xsd:integer)
- 1320296 (xsd:integer)
- 1920144 (xsd:integer)
- 2178806 (xsd:integer)
- 3296231 (xsd:integer)
|
| prop-fr:nom
|
- Bron (fr)
- Chiba (fr)
- Eisenberg (fr)
- Lund (fr)
- Rhodes (fr)
- Stein (fr)
- Uno (fr)
- Luce (fr)
- Tomita (fr)
- Seki (fr)
- Chen (fr)
- Blair (fr)
- Cook (fr)
- Day (fr)
- Frank (fr)
- Moon (fr)
- Rogers (fr)
- Williams (fr)
- Dunbar (fr)
- Müller (fr)
- Strauss (fr)
- Tanaka (fr)
- Cazals (fr)
- Clark (fr)
- Faust (fr)
- Huang (fr)
- Johnson (fr)
- Perry (fr)
- Stewart (fr)
- Liu (fr)
- Lu (fr)
- Löffler (fr)
- Ross (fr)
- Song (fr)
- Wei (fr)
- Yang (fr)
- Yu (fr)
- Goldstone (fr)
- Kaplan (fr)
- Locatelli (fr)
- Plummer (fr)
- Schrijver (fr)
- Zuckerman (fr)
- Alon (fr)
- Barrow (fr)
- Libchaber (fr)
- Moser (fr)
- Calvet (fr)
- Erdős (fr)
- Friesen (fr)
- Mackey (fr)
- Robson (fr)
- Balas (fr)
- Wegener (fr)
- Cormen (fr)
- Crippen (fr)
- Eppstein (fr)
- Karande (fr)
- Karp (fr)
- Kerbosch (fr)
- Leiserson (fr)
- Motwani (fr)
- Ouyang (fr)
- Rivest (fr)
- Strash (fr)
- Takahashi (fr)
- Tarjan (fr)
- Wigderson (fr)
- Sudan (fr)
- Barak (fr)
- Impagliazzo (fr)
- Wasserman (fr)
- Childs (fr)
- Downey (fr)
- Valiant (fr)
- Halldórsson (fr)
- Nishizeki (fr)
- Papadimitriou (fr)
- Protasi (fr)
- Szekeres (fr)
- Moult (fr)
- Arora (fr)
- Krauthgamer (fr)
- Gutmann (fr)
- Jian (fr)
- Patel (fr)
- Battiti (fr)
- Burstall (fr)
- Willett (fr)
- Harary (fr)
- Skiena (fr)
- Farhi (fr)
- Feige (fr)
- Xiao (fr)
- Xia (fr)
- Resende (fr)
- Szegedy (fr)
- Bollobás (fr)
- Lipton (fr)
- Sudakov (fr)
- Grandoni (fr)
- Abello (fr)
- Konc (fr)
- Makino (fr)
- Della Croce (fr)
- Fellows (fr)
- Kratsch (fr)
- Lovász (fr)
- Krivelevich (fr)
- Lempel (fr)
- Even (fr)
- Sipser (fr)
- Grosso (fr)
- Humblet (fr)
- Valiente (fr)
- Zane (fr)
- Goldmann (fr)
- Stockmeyer (fr)
- Colbourn (fr)
- Itai (fr)
- Trojanowski (fr)
- Gavril (fr)
- Golumbic (fr)
- Kloks (fr)
- Yuster (fr)
- Zwick (fr)
- Kolata (fr)
- Goldwasser (fr)
- Ide (fr)
- Nešetřil (fr)
- Shirakawa (fr)
- Khot (fr)
- Amano (fr)
- Kameda (fr)
- Katayama (fr)
- Garey (fr)
- Pnueli (fr)
- Safra (fr)
- Grötschel (fr)
- Magniez (fr)
- Meka (fr)
- Mirny (fr)
- Shor (fr)
- Ariyoshi (fr)
- Paturi (fr)
- Jerrum (fr)
- Poljak (fr)
- Bomze (fr)
- Boppana (fr)
- Budinich (fr)
- Butenko (fr)
- Carraghan (fr)
- Eisenbrand (fr)
- Fahle (fr)
- Gröger (fr)
- Gutin (fr)
- Hamamoto (fr)
- Hamzaoglu (fr)
- Håstad (fr)
- Janežič (fr)
- Kanj (fr)
- Kuhl (fr)
- Lagarias (fr)
- Maruoka (fr)
- Muegge (fr)
- Narihisa (fr)
- Pardalos (fr)
- Pelillo (fr)
- Peyton (fr)
- Potechin (fr)
- Rarey (fr)
- Razborov (fr)
- Rodeh (fr)
- Rosgen (fr)
- Régin (fr)
- Samudrala (fr)
- Sankoff (fr)
- Santha (fr)
- Sethuraman (fr)
- Spirin (fr)
- Tsukiyama (fr)
- Vassilevska (fr)
- Yannakakis (fr)
- Östergård (fr)
- Bron (fr)
- Chiba (fr)
- Eisenberg (fr)
- Lund (fr)
- Rhodes (fr)
- Stein (fr)
- Uno (fr)
- Luce (fr)
- Tomita (fr)
- Seki (fr)
- Chen (fr)
- Blair (fr)
- Cook (fr)
- Day (fr)
- Frank (fr)
- Moon (fr)
- Rogers (fr)
- Williams (fr)
- Dunbar (fr)
- Müller (fr)
- Strauss (fr)
- Tanaka (fr)
- Cazals (fr)
- Clark (fr)
- Faust (fr)
- Huang (fr)
- Johnson (fr)
- Perry (fr)
- Stewart (fr)
- Liu (fr)
- Lu (fr)
- Löffler (fr)
- Ross (fr)
- Song (fr)
- Wei (fr)
- Yang (fr)
- Yu (fr)
- Goldstone (fr)
- Kaplan (fr)
- Locatelli (fr)
- Plummer (fr)
- Schrijver (fr)
- Zuckerman (fr)
- Alon (fr)
- Barrow (fr)
- Libchaber (fr)
- Moser (fr)
- Calvet (fr)
- Erdős (fr)
- Friesen (fr)
- Mackey (fr)
- Robson (fr)
- Balas (fr)
- Wegener (fr)
- Cormen (fr)
- Crippen (fr)
- Eppstein (fr)
- Karande (fr)
- Karp (fr)
- Kerbosch (fr)
- Leiserson (fr)
- Motwani (fr)
- Ouyang (fr)
- Rivest (fr)
- Strash (fr)
- Takahashi (fr)
- Tarjan (fr)
- Wigderson (fr)
- Sudan (fr)
- Barak (fr)
- Impagliazzo (fr)
- Wasserman (fr)
- Childs (fr)
- Downey (fr)
- Valiant (fr)
- Halldórsson (fr)
- Nishizeki (fr)
- Papadimitriou (fr)
- Protasi (fr)
- Szekeres (fr)
- Moult (fr)
- Arora (fr)
- Krauthgamer (fr)
- Gutmann (fr)
- Jian (fr)
- Patel (fr)
- Battiti (fr)
- Burstall (fr)
- Willett (fr)
- Harary (fr)
- Skiena (fr)
- Farhi (fr)
- Feige (fr)
- Xiao (fr)
- Xia (fr)
- Resende (fr)
- Szegedy (fr)
- Bollobás (fr)
- Lipton (fr)
- Sudakov (fr)
|
| prop-fr:page
|
- 3.100000 (xsd:double)
- 276 (xsd:integer)
|
| prop-fr:pages
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 23 (xsd:integer)
- 24 (xsd:integer)
- 28 (xsd:integer)
- 47 (xsd:integer)
- 57 (xsd:integer)
- 70 (xsd:integer)
- 83 (xsd:integer)
- 85 (xsd:integer)
- 87 (xsd:integer)
- 95 (xsd:integer)
- 105 (xsd:integer)
- 109 (xsd:integer)
- 110 (xsd:integer)
- 115 (xsd:integer)
- 119 (xsd:integer)
- 127 (xsd:integer)
- 130 (xsd:integer)
- 131 (xsd:integer)
- 135 (xsd:integer)
- 151 (xsd:integer)
- 165 (xsd:integer)
- 180 (xsd:integer)
- 181 (xsd:integer)
- 195 (xsd:integer)
- 197 (xsd:integer)
- 201 (xsd:integer)
- 205 (xsd:integer)
- 210 (xsd:integer)
- 219 (xsd:integer)
- 221 (xsd:integer)
- 224 (xsd:integer)
- 237 (xsd:integer)
- 253 (xsd:integer)
- 260 (xsd:integer)
- 261 (xsd:integer)
- 275 (xsd:integer)
- 278 (xsd:integer)
- 279 (xsd:integer)
- 283 (xsd:integer)
- 287 (xsd:integer)
- 347 (xsd:integer)
- 354 (xsd:integer)
- 363 (xsd:integer)
- 375 (xsd:integer)
- 400 (xsd:integer)
- 413 (xsd:integer)
- 415 (xsd:integer)
- 425 (xsd:integer)
- 443 (xsd:integer)
- 446 (xsd:integer)
- 455 (xsd:integer)
- 457 (xsd:integer)
- 461 (xsd:integer)
- 463 (xsd:integer)
- 499 (xsd:integer)
- 501 (xsd:integer)
- 503 (xsd:integer)
- 505 (xsd:integer)
- 512 (xsd:integer)
- 537 (xsd:integer)
- 564 (xsd:integer)
- 569 (xsd:integer)
- 575 (xsd:integer)
- 593 (xsd:integer)
- 600 (xsd:integer)
- 610 (xsd:integer)
- 615 (xsd:integer)
- 634 (xsd:integer)
- 681 (xsd:integer)
- 798 (xsd:integer)
- 832 (xsd:integer)
- 847 (xsd:integer)
- 1054 (xsd:integer)
- 1346 (xsd:integer)
- 2122 (xsd:integer)
- 2233 (xsd:integer)
- 12123 (xsd:integer)
|
| prop-fr:pagesTotales
| |
| prop-fr:passage
|
- 194 (xsd:integer)
- 296 (xsd:integer)
- 299 (xsd:integer)
- 389 (xsd:integer)
- 1003 (xsd:integer)
- 1508 (xsd:integer)
|
| prop-fr:pmc
| |
| prop-fr:pmid
|
- 9334300 (xsd:integer)
- 9636717 (xsd:integer)
- 12653507 (xsd:integer)
- 14517352 (xsd:integer)
- 18152948 (xsd:integer)
|
| prop-fr:postscript
|
- . English translation in Sov. Math. Dokl. 31 : 354–357 (fr)
- . English translation in Sov. Math. Dokl. 31 : 354–357 (fr)
|
| prop-fr:prénom
|
- Akira (fr)
- Alain (fr)
- B (fr)
- L (fr)
- Mario (fr)
- S (fr)
- T (fr)
- A. (fr)
- B. (fr)
- E. (fr)
- G. (fr)
- H. (fr)
- J. (fr)
- K. (fr)
- L. (fr)
- M. (fr)
- Nicholas (fr)
- Paul (fr)
- R. (fr)
- Victor (fr)
- Y. (fr)
- Barry (fr)
- Peter (fr)
- C. (fr)
- P. M. (fr)
- D. (fr)
- David (fr)
- Frédéric (fr)
- Gabriel (fr)
- George (fr)
- Gina (fr)
- John (fr)
- Michael D. (fr)
- N. (fr)
- S. (fr)
- Stanley (fr)
- V. (fr)
- Christine (fr)
- P. D. (fr)
- S. A. (fr)
- A. M. (fr)
- Carsten (fr)
- Charles J. (fr)
- Maarten (fr)
- Q. (fr)
- Richard M. (fr)
- Sanjeev (fr)
- T. (fr)
- Thomas H. (fr)
- U. (fr)
- Yu (fr)
- Aaron (fr)
- C. S. (fr)
- David S. (fr)
- F. (fr)
- G. P. (fr)
- Katherine (fr)
- Ram (fr)
- Charles E. (fr)
- Clifford (fr)
- J. M. (fr)
- J.-C. (fr)
- L. G. (fr)
- Matthias (fr)
- R. J. (fr)
- I. (fr)
- J. W. (fr)
- James B. (fr)
- M. R. (fr)
- Marcello (fr)
- Ove (fr)
- R. E. (fr)
- M. C. (fr)
- J. H. (fr)
- A. A. (fr)
- Darren (fr)
- Rajeev (fr)
- Ronald L. (fr)
- A. E. (fr)
- I. M. (fr)
- R. G. (fr)
- Ge (fr)
- Peter W. (fr)
- D. S. (fr)
- Christos H. (fr)
- D. K. (fr)
- Ingo (fr)
- G. M. (fr)
- Stephen A. (fr)
- Miklos (fr)
- Avi (fr)
- Jeffrey C. (fr)
- Leonid A. (fr)
- Boaz (fr)
- Béla (fr)
- Sergiy (fr)
- Madhu (fr)
- M. M. (fr)
- Mihalis (fr)
- Hua (fr)
- Steven S. (fr)
- Albert D. (fr)
- F. S. (fr)
- I. C. (fr)
- Kazuyuki (fr)
- Brent N. (fr)
- Hans Dietmar (fr)
- Iyad A. (fr)
- Jean R. S. (fr)
- Jiaheng (fr)
- Jianer (fr)
- M. G. C. (fr)
- P. R. J. (fr)
- R. Duncan (fr)
- Raghu (fr)
- Samyukta (fr)
- William H. E. (fr)
- Xiaokui (fr)
- Xiuzhen (fr)
- Zhewei (fr)
- Akira (fr)
- Alain (fr)
- B (fr)
- L (fr)
- Mario (fr)
- S (fr)
- T (fr)
- A. (fr)
- B. (fr)
- E. (fr)
- G. (fr)
- H. (fr)
- J. (fr)
- K. (fr)
- L. (fr)
- M. (fr)
- Nicholas (fr)
- Paul (fr)
- R. (fr)
- Victor (fr)
- Y. (fr)
- Barry (fr)
- Peter (fr)
- C. (fr)
- P. M. (fr)
- D. (fr)
- David (fr)
- Frédéric (fr)
- Gabriel (fr)
- George (fr)
- Gina (fr)
- John (fr)
- Michael D. (fr)
- N. (fr)
- S. (fr)
- Stanley (fr)
- V. (fr)
- Christine (fr)
- P. D. (fr)
- S. A. (fr)
- A. M. (fr)
- Carsten (fr)
- Charles J. (fr)
- Maarten (fr)
- Q. (fr)
- Richard M. (fr)
- Sanjeev (fr)
- T. (fr)
- Thomas H. (fr)
- U. (fr)
- Yu (fr)
- Aaron (fr)
- C. S. (fr)
- David S. (fr)
- F. (fr)
- G. P. (fr)
- Katherine (fr)
- Ram (fr)
- Charles E. (fr)
- Clifford (fr)
- J. M. (fr)
- J.-C. (fr)
- L. G. (fr)
- Matthias (fr)
- R. J. (fr)
- I. (fr)
- J. W. (fr)
- James B. (fr)
- M. R. (fr)
- Marcello (fr)
- Ove (fr)
- R. E. (fr)
- M. C. (fr)
- J. H. (fr)
- A. A. (fr)
- Darren (fr)
- Rajeev (fr)
- Ronald L. (fr)
- A. E. (fr)
- I. M. (fr)
- R. G. (fr)
- Ge (fr)
- Peter W. (fr)
- D. S. (fr)
- Christos H. (fr)
- D. K. (fr)
- Ingo (fr)
- G. M. (fr)
- Stephen A. (fr)
- Miklos (fr)
- Avi (fr)
- Jeffrey C. (fr)
- Leonid A. (fr)
- Boaz (fr)
- Béla (fr)
- Sergiy (fr)
- Madhu (fr)
- M. M. (fr)
- Mihalis (fr)
- Hua (fr)
|
| prop-fr:s2cid
|
- 224579 (xsd:integer)
- 594494 (xsd:integer)
- 751563 (xsd:integer)
- 1800512 (xsd:integer)
- 2754095 (xsd:integer)
- 5713815 (xsd:integer)
- 6326587 (xsd:integer)
- 6390600 (xsd:integer)
- 6713201 (xsd:integer)
- 7573663 (xsd:integer)
- 8561542 (xsd:integer)
- 9501737 (xsd:integer)
- 9855414 (xsd:integer)
- 11967153 (xsd:integer)
- 11987483 (xsd:integer)
- 12258606 (xsd:integer)
- 12961628 (xsd:integer)
- 13886709 (xsd:integer)
- 16186758 (xsd:integer)
- 17397273 (xsd:integer)
- 18371269 (xsd:integer)
- 21436014 (xsd:integer)
- 33643794 (xsd:integer)
- 37556989 (xsd:integer)
- 40764225 (xsd:integer)
- 46153055 (xsd:integer)
- 46605913 (xsd:integer)
- 47515491 (xsd:integer)
- 123335474 (xsd:integer)
|
| prop-fr:series
|
- Algorithms and Combinatorics (fr)
- Lecture Notes in Computer Science (fr)
- New Series (fr)
- Series B (fr)
- DIMACS Series in Discrete Mathematics and Theoretical Computer Science (fr)
- Proceedings of the VLDB Endowment (fr)
- Computer Science and Applied Mathematics (fr)
- Discrete Mathematics & Its Applications (fr)
- IMA Vol. Math. Appl. (fr)
- Structural Analysis in the Social Sciences (fr)
- DIMACS Series on Discrete Mathematics and Theoretical Computer Science (fr)
- Algorithms and Combinatorics (fr)
- Lecture Notes in Computer Science (fr)
- New Series (fr)
- Series B (fr)
- DIMACS Series in Discrete Mathematics and Theoretical Computer Science (fr)
- Proceedings of the VLDB Endowment (fr)
- Computer Science and Applied Mathematics (fr)
- Discrete Mathematics & Its Applications (fr)
- IMA Vol. Math. Appl. (fr)
- Structural Analysis in the Social Sciences (fr)
- DIMACS Series on Discrete Mathematics and Theoretical Computer Science (fr)
|
| prop-fr:sousTitre
|
- a guide to the theory of NP-completeness (fr)
- a guide to the theory of NP-completeness (fr)
|
| prop-fr:texte
|
- difficile à approcher (fr)
- difficile à approcher (fr)
|
| prop-fr:titre
|
- Geometric Algorithms and Combinatorial Optimization (fr)
- Lower bounds for the monotone complexity of some Boolean functions (fr)
- The worst-case time complexity for generating all maximal cliques and computational experiments (fr)
- A note on the problem of reporting maximal cliques (fr)
- Introduction to Algorithms (fr)
- On cliques in graphs (fr)
- Algorithm 457: finding all cliques of an undirected graph (fr)
- Computers and intractability (fr)
- Proof verification and the hardness of approximation problems (fr)
- Discrete Mathematics and Theoretical Computer Science (fr)
- Parameterized complexity (fr)
- Computational Complexity: A Modern Approach (fr)
- Introduction to the Theory of Computation (fr)
- Algorithmic Graph Theory and Perfect Graphs (fr)
- Handbook of graph theory (fr)
- Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands (fr)
- A combinatorial problem in geometry (fr)
- Probabilistic checking of proofs: A new characterization of NP (fr)
- The Algorithm Design Manual (fr)
- Keller's cube-tiling conjecture is false in high dimensions (fr)
- An effective local search for the maximum clique problem (fr)
- Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993 (fr)
- A simple lower bound for monotone clique using a communication game (fr)
- Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003 (fr)
- A graph-theoretic algorithm for comparative modeling of protein structure (fr)
- Strong computational lower bounds via parameterized complexity (fr)
- "Strong" NP-completeness results: motivation, examples and implications (fr)
- A procedure for clique detection using the group matrix (fr)
- An algorithm for solving maximum independent set problem (fr)
- Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design (fr)
- A fast algorithm for the maximum clique problem (fr)
- A method of matrix analysis of group structure (fr)
- Algorithm Theory: SWAT 2004 (fr)
- Algorithms for maximum independent sets (fr)
- An exact algorithm for the maximum clique problem (fr)
- Applications of a planar separator theorem (fr)
- Approximating maximum clique by removing subgraphs (fr)
- Arboricity and subgraph listing algorithms (fr)
- Subgraph isomorphism, matching relational structures and maximal cliques (fr)
- Clique is hard to approximate within (fr)
- Complete subgraphs are elusive (fr)
- Complexity of Computer Computations (fr)
- Complexity results on graphs with few cliques (fr)
- DNA solution of the maximal clique problem (fr)
- Encyclopedia of Optimization (fr)
- External Memory Algorithms (fr)
- Finding a large hidden clique in a random graph (fr)
- Finding a maximum clique in an arbitrary graph (fr)
- Finding a maximum independent set (fr)
- Finding a maximum independent set in time (fr)
- Finding a minimum circuit in a graph (fr)
- Finding cliques by quantum adiabatic evolution (fr)
- Graph theory and sparse matrix computation (fr)
- Handbook of Combinatorial Optimization (fr)
- In a Frenzy, Math Enters Age of Electronic Mail (fr)
- Large cliques elude the Metropolis process (fr)
- Finding and counting small induced subgraphs efficiently (fr)
- Markov graphs (fr)
- On generating all maximal independent sets (fr)
- On the complexity of the subgraph problem (fr)
- On the independent set problem in random graphs (fr)
- Permutation graphs and transitive graphs (fr)
- Proc. 10th European Symposium on Algorithms (fr)
- Proc. 15th ACM Symposium on Theory of Computing (fr)
- Proc. 38th ACM Symp. Theory of Computing (fr)
- Proc. 3rd ACM Symposium on Theory of Computing (fr)
- Proc. 41st ACM Symposium on Theory of Computing (fr)
- On the complexity of fixed parameter clique and dominating set (fr)
- Quantum algorithms for subset finding (fr)
- Quantum algorithms for the triangle problem (fr)
- Réduction 3-SAT vers clique (fr)
- Small molecule docking and scoring (fr)
- Social Network Analysis: Methods and Applications (fr)
- Some simplified NP-complete graph problems (fr)
- The clique problem for planar graphs (fr)
- The maximum ratio clique problem (fr)
- Unit disk graphs (fr)
- Fixed-parameter tractability and completeness. II. On completeness for W[1] (fr)
- Well-covered graphs: a survey (fr)
- An improved branch and bound algorithm for the maximum clique problem (fr)
- Proceedings of the 41st International Conference on Very Large Data Bases (fr)
- Proc. 32nd IEEE Symp. on Foundations of Computer Science (fr)
- Finding and certifying a large hidden clique in a semirandom graph (fr)
- Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (fr)
- Approximating maximum independent sets by excluding subgraphs (fr)
- Approximations of Weighted Independent Set and Hereditary Subset Problems (fr)
- The monotone circuit complexity of boolean functions (fr)
- CLIP: similarity searching of 3D databases using clique detection (fr)
- A new algorithm for generating all the maximal independent sets (fr)
- On the randomized complexity of monotone graph properties (fr)
- Finding and counting cliques and independent sets in r-uniform hypergraphs (fr)
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments (fr)
- A combinatorial algorithm for calculating ligand binding (fr)
- A superpolynomial lower bound for a circuit computing the clique function with at most negation gates (fr)
- Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem (fr)
- Proc. 42nd IEEE Symp. Foundations of Computer Science (fr)
- Chapter 6: Clique, Independent Set, and Vertex Cover (fr)
- Mathematical Challenges from Theoretical/Computational Chemistry (fr)
- Reactive local search for the maximum clique problem (fr)
- Algorithms and Complexity: New Directions and Recent Results (fr)
- A cube tiling of dimension eight with no facesharing (fr)
- A taxonomy of problems with fast parallel algorithms (fr)
- Protein complexes and functional modules in molecular networks (fr)
- Which problems have strongly exponential complexity? (fr)
- Computational complexity of inferring phylogenies by compatibility (fr)
- Algorithms for a maximum clique and a maximum independent set of a circle graph (fr)
- A branch and bound algorithm for the maximum clique problem (fr)
- Listing all maximal cliques in large sparse real-world graphs in near-optimal time (fr)
- On the complexity of branching programs and decision trees for clique functions (fr)
- Geometric Algorithms and Combinatorial Optimization (fr)
- Lower bounds for the monotone complexity of some Boolean functions (fr)
- The worst-case time complexity for generating all maximal cliques and computational experiments (fr)
- A note on the problem of reporting maximal cliques (fr)
- Introduction to Algorithms (fr)
- On cliques in graphs (fr)
- Algorithm 457: finding all cliques of an undirected graph (fr)
- Computers and intractability (fr)
- Proof verification and the hardness of approximation problems (fr)
- Discrete Mathematics and Theoretical Computer Science (fr)
- Parameterized complexity (fr)
- Computational Complexity: A Modern Approach (fr)
- Introduction to the Theory of Computation (fr)
- Algorithmic Graph Theory and Perfect Graphs (fr)
- Handbook of graph theory (fr)
- Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands (fr)
- A combinatorial problem in geometry (fr)
- Probabilistic checking of proofs: A new characterization of NP (fr)
- The Algorithm Design Manual (fr)
- Keller's cube-tiling conjecture is false in high dimensions (fr)
- An effective local search for the maximum clique problem (fr)
- Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993 (fr)
- A simple lower bound for monotone clique using a communication game (fr)
- Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003 (fr)
- A graph-theoretic algorithm for comparative modeling of protein structure (fr)
- Strong computational lower bounds via parameterized complexity (fr)
- "Strong" NP-completeness results: motivation, examples and implications (fr)
- A procedure for clique detection using the group matrix (fr)
- An algorithm for solving maximum independent set problem (fr)
- Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design (fr)
- A fast algorithm for the maximum clique problem (fr)
- A method of matrix analysis of group structure (fr)
- Algorithm Theory: SWAT 2004 (fr)
- Algorithms for maximum independent sets (fr)
- An exact algorithm for the maximum clique problem (fr)
- Applications of a planar separator theorem (fr)
- Approximating maximum clique by removing subgraphs (fr)
- Arboricity and subgraph listing algorithms (fr)
- Subgraph isomorphism, matching relational structures and maximal cliques (fr)
- Clique is hard to approximate within (fr)
- Complete subgraphs are elusive (fr)
- Complexity of Computer Computations (fr)
- Complexity results on graphs with few cliques (fr)
- DNA solution of the maximal clique problem (fr)
- Encyclopedia of Optimization (fr)
- External Memory Algorithms (fr)
- Finding a large hidden clique in a random graph (fr)
- Finding a maximum clique in an arbitrary graph (fr)
- Finding a maximum independent set (fr)
- Finding a maximum independent set in time (fr)
- Finding a minimum circuit in a graph (fr)
- Finding cliques by quantum adiabatic evolution (fr)
- Graph theory and sparse matrix computation (fr)
- Handbook of Combinatorial Optimization (fr)
- In a Frenzy, Math Enters Age of Electronic Mail (fr)
- Large cliques elude the Metropolis process (fr)
- Finding and counting small induced subgraphs efficiently (fr)
- Markov graphs (fr)
- On generating all maximal independent sets (fr)
- On the complexity of the subgraph problem (fr)
- On the independent set problem in random graphs (fr)
- Permutation graphs and transitive graphs (fr)
- Proc. 10th European Symposium on Algorithms (fr)
- Proc. 15th ACM Symposium on Theory of Computing (fr)
- Proc. 38th ACM Symp. Theory of Computing (fr)
- Proc. 3rd ACM Symposium on Theory of Computing (fr)
- Proc. 41st ACM Symposium on Theory of Computing (fr)
- On the complexity of fixed parameter clique and dominating set (fr)
- Quantum algorithms for subset finding (fr)
- Quantum algorithms for the triangle problem (fr)
- Réduction 3-SAT vers clique (fr)
- Small molecule docking and scoring (fr)
- Social Network Analysis: Methods and Applications (fr)
- Some simplified NP-complete graph problems (fr)
- The clique problem for planar graphs (fr)
- The maximum ratio clique problem (fr)
- Unit disk graphs (fr)
- Fixed-parameter tractability and completeness. II. On completeness for W[1] (fr)
- Well-covered graphs: a survey (fr)
- An improved branch and bound algorithm for the maximum clique problem (fr)
- Proceedings of the 41st International Conference on Very Large Data Bases (fr)
- Proc. 32nd IEEE Symp. on Foundations of Computer Science (fr)
- Finding and certifying a large hidden clique in a semirandom graph (fr)
- Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (fr)
- Approximating maximum independent sets by excluding subgraphs (fr)
- Approximations of Weighted Independent Set and Hereditary Subset Problems (fr)
- The monotone circuit complexity of boolean functions (fr)
- CLIP: similarity searching of 3D databases using clique detection (fr)
- A new algorithm for generating all the maximal independent sets (fr)
- On the randomized complexity of monotone graph properties (fr)
- Finding and counting cliques and independent sets in r-uniform hypergraphs (fr)
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments (fr)
- A combinatorial algorithm for calculating ligand binding (fr)
- A superpolynomial lower bound for a circuit computing the clique function with at most negation gates (fr)
- Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem (fr)
- Proc. 42nd IEEE Symp. Foundations of Computer Science (fr)
- Chapter 6: Clique, Independent Set, and Vertex Cover (fr)
- Mathematical Challenges from Theoretical/Computational Chemistry (fr)
- Reactive local search for the maximum clique problem (fr)
- Algorithms and Complexity: New Directions and Recent Results (fr)
|
| prop-fr:titreOuvrage
|
- Algorithms on Trees and Graphs (fr)
- Algorithms on Trees and Graphs (fr)
|
| prop-fr:trad
|
- boxicity (fr)
- Hardness of approximation (fr)
- dependancy graph (fr)
- boxicity (fr)
- Hardness of approximation (fr)
- dependancy graph (fr)
|
| prop-fr:url
| |
| prop-fr:volume
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 3 (xsd:integer)
- 4 (xsd:integer)
- 5 (xsd:integer)
- 6 (xsd:integer)
- 7 (xsd:integer)
- 8 (xsd:integer)
- 9 (xsd:integer)
- 10 (xsd:integer)
- 12 (xsd:integer)
- 13 (xsd:integer)
- 14 (xsd:integer)
- 15 (xsd:integer)
- 16 (xsd:integer)
- 17 (xsd:integer)
- 18 (xsd:integer)
- 19 (xsd:integer)
- 20 (xsd:integer)
- 21 (xsd:integer)
- 25 (xsd:integer)
- 26 (xsd:integer)
- 27 (xsd:integer)
- 28 (xsd:integer)
- 29 (xsd:integer)
- 32 (xsd:integer)
- 35 (xsd:integer)
- 37 (xsd:integer)
- 41 (xsd:integer)
- 43 (xsd:integer)
- 45 (xsd:integer)
- 50 (xsd:integer)
- 56 (xsd:integer)
- 58 (xsd:integer)
- 63 (xsd:integer)
- 64 (xsd:integer)
- 72 (xsd:integer)
- 74 (xsd:integer)
- 81 (xsd:integer)
- 86 (xsd:integer)
- 92 (xsd:integer)
- 95 (xsd:integer)
- 99 (xsd:integer)
- 100 (xsd:integer)
- 120 (xsd:integer)
- 141 (xsd:integer)
- 182 (xsd:integer)
- 278 (xsd:integer)
- 279 (xsd:integer)
- 281 (xsd:integer)
- 326 (xsd:integer)
- 363 (xsd:integer)
- 407 (xsd:integer)
- 2461 (xsd:integer)
- 2731 (xsd:integer)
- 2833 (xsd:integer)
- 3111 (xsd:integer)
- A1.2: GT19 (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets d'un graphe tous adjacents les uns aux autres, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées. Les formulations courantes du problème de la clique incluent la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets), la recherche d'une clique de poids maximal dans un graphe pondéré, la liste de toutes les cliques maximums et la résolution du problème de décision consistant à déterminer si un graphe contient une clique plus grande qu'une taille donnée. (fr)
- En informatique, le problème de la clique est un problème algorithmique qui consiste à trouver des cliques (sous-ensembles de sommets d'un graphe tous adjacents les uns aux autres, également appelés sous-graphes complets) dans un graphe. Ce problème a plusieurs formulations différentes selon les cliques et les informations sur les cliques devant être trouvées. Les formulations courantes du problème de la clique incluent la recherche d'une clique maximum (une clique avec le plus grand nombre possible de sommets), la recherche d'une clique de poids maximal dans un graphe pondéré, la liste de toutes les cliques maximums et la résolution du problème de décision consistant à déterminer si un graphe contient une clique plus grande qu'une taille donnée. (fr)
|
| rdfs:label
|
- Cliquenproblem (de)
- Problema della cricca (it)
- Problème de la clique (fr)
- مشكلة المخطط الكامل ضمن مخطط (ar)
- Задача о клике (ru)
- Задача про кліку (uk)
- 分團問題 (zh)
- Cliquenproblem (de)
- Problema della cricca (it)
- Problème de la clique (fr)
- مشكلة المخطط الكامل ضمن مخطط (ar)
- Задача о клике (ru)
- Задача про кліку (uk)
- 分團問題 (zh)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
