Le lemme de régularité de Szemeredi dit que chaque graphe dense peut être approché comme une union de nombreux graphes expanseurs bipartis. Plus précisément, il existe une partition de la plupart des sommets en ensembles sorte que la plupart des paires d'ensembles forment des expanseurs bipartites...
Le résultat par Robertson et Seymour démontre un algorithme pour tester si un graphique fixe G est un mineur de . J'ai deux questions et demie sur ce sujet:O ( n3)O(n3)O(n^3)ggGHHH 1) Il semble que cet algorithme ait été amélioré depuis. Quel est actuellement l'algorithme le plus connu? 2a)...
La complexité du problème suivant a-t-elle été étudiée? Entrée : un graphe cubique (ou régulier) , une borne supérieure naturelleG = ( V , E ) t333G = ( V, E)G=(V,E)G=(V,E)ttt Question : existe-t-il une partition de en parties de taille telle que la somme des ordres des sous-graphes correspondants...
J'ai récemment enseigné aux expanseurs et introduit la notion de graphes Ramanujan. Michael Forbes a demandé pourquoi on les appelait ainsi, et j'ai dû admettre que je ne sais pas. N'importe
La conjecture de reconstruction dit que les graphes (avec au moins trois sommets) sont déterminés uniquement par leurs sous-graphes supprimés par les sommets. Cette conjecture a cinq décennies. En recherchant dans la littérature pertinente, j'ai trouvé que les classes de graphiques suivantes sont...
On sait qu'il est NP-complet de tester si un cycle hamiltonien existe dans un graphe à 3 réguliers, même s'il est planaire (Garey, Johnson et Tarjan, SIAM J.Comput.1976) ou bipartite (Akiyama, Nishizeki, et Saito, J. Inform. Proc. 1980) ou pour tester si un cycle hamiltonien existe dans un graphe à...
Un graphe H est un noyau si tout homomorphisme de H vers lui-même est une bijection. Un sous-graphe H de G est un noyau de G si H est un noyau et qu'il y a un homomorphisme de G vers H. http://en.wikipedia.org/wiki/Core_%28graph_theory%29 Étant donné un graphe G, quel est l'algorithme exact le plus...
Je recherche des expandeurs déséquilibrés qui sont "bons" et "peu encombrants". Plus précisément, un graphe bipartite gauche-régulier , , , avec le degré gauche est un -expander si pour tout de taille au plus , le nombre de voisins distincts de dans est au moins. On sait que la méthode probabiliste...
Compter le nombre de correspondances parfaites dans un graphe bipartite est immédiatement réductible au calcul du permanent. Étant donné que trouver une correspondance parfaite dans un graphique non bipartite est dans NP, il existe une certaine réduction des graphiques non bipartites au permanent,...
La largeur de l'arbre mesure la proximité d'un graphique avec un arbre. Il est difficile de calculer la largeur de l'arbre NP. L' algorithme d' approximation le plus connu atteint le facteur .O(logn−−−−√)O(logn)O(\sqrt{{\log}n}) Le théorème de Courcelle stipule que toute propriété de graphes...
J'ai lu dans de nombreux articles que déterminer la constante de Cheeger d'un graphe est -hard. Cela semble être un théorème populaire, mais je n'ai jamais trouvé ni citation ni preuve pour cette affirmation. À qui dois-je donner du crédit? Dans un vieux document (Isoperimetric Numbers of Graphs,...
Où puis-je trouver des graphiques relatifs à des problèmes réels? Je connais deux référentiels: Collection Sparse Matrix de l'Université de Floride Bodlaender's TreewidthLib
J'essaie de trouver à quel point et sont vraiment proches , quand et est une constante ne dépendant pas de n (donc ). Mon estimation est que whp, mais je n'ai pas pu le prouver.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o ( n )t w ( G...
Il y a clairement une réduction de CLIQUE à k-Color car ils sont tous deux NP-Complete. En fait, je peux en construire un en composant une réduction de CLIQUE à 3-SAT avec une réduction de 3-SAT à k-Color. Je me demande s'il y a une réduction directe raisonnable entre ces problèmes. Disons, une...
Pour une constante , on peut déterminer en temps linéaire, étant donné un graphe d'entrée G , si sa largeur d'arbre est ≤ k . Cependant, lorsque k et G sont donnés en entrée, le problème est NP-difficile. ( Source ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Cependant, lorsque le graphe d'entrée est...
Donné est un poignard. Vous souhaitez étiqueter chaque nœud en fonction du nombre de nœuds accessibles depuis celui-ci. est une borne supérieure triviale; Ω ( V + E ) est une borne inférieure (je pense). Existe-t-il un meilleur algorithme? Y a-t-il des raisons de croire que la borne inférieure peut...
Message mis à jour le 31 août : j'ai ajouté un résumé des réponses actuelles sous la question d'origine. Merci pour toutes les réponses intéressantes! Bien sûr, tout le monde peut continuer à publier de nouvelles découvertes. Pour quelles familles de graphes existe-t-il un algorithme polynomial de...
Étant donné un ensemble SSS de personnes, je voudrais les asseoir pour une séquence de repas à des tables de taille kkk . (Bien sûr, il y a suffisamment de tables pour asseoir tous les |S||S||S| pour chaque repas.) J'aimerais organiser cela de telle sorte que personne ne partage une table avec la...
(J'ai posté cette question sur MathOverflow il y a deux semaines, mais jusqu'à présent sans réponse rigoureuse) J'ai une question sur les mesures de largeur de graphique des graphiques simples non dirigés. Il est bien connu que les cographes (graphes qui peuvent être construits par les opérations...
Nous savons que l'ensemble indépendant maximum (MIS) est difficile à estimer dans un facteur pour tout ϵ >n1−ϵn1−ϵn^{1-\epsilon} moins que P = NP. Quelles sont certaines classes spéciales de graphiques pour lesquelles de meilleurs algorithmes d'approximation sont connus?ϵ>0ϵ>0\epsilon > 0...