Une enquête sur les séparateurs?

11

Il y a maintenant des montagnes de résultats sur les séparateurs dans les graphiques, depuis le séparateur planaire, le séparateur d'arbre, les graphiques de largeur d'arbre borné, les graphiques de genre délimités, etc., etc., etc.

reference-request graph-algorithms survey Sariel Har-Peled
la source
Il est temps pour vous d'écrire un Sariel :).
Chandra Chekuri
J'espérais que tu l'écrirais Chandra;).
Sariel Har-Peled

Réponses:

7

Pas exactement le plus récent (publié en 2001), mais le texte d'Arnold L. Rosenberg, Lenwood S. Heath, "Graph Separators, with Applications" peut être un bon endroit à regarder. Le lien vers le livre Google est fourni ici: http://books.google.ca/books/about/Graph_Separators_with_Applications.html?id=7DNKE5ZiNZYC&redir_esc=y

Vincent Russo
la source
4
Ouais. J'espérais quelque chose de plus à jour que cela. (J'ai certainement vu ce livre auparavant - je pense qu'il avait la réponse à l'une de mes questions précédentes sur ce forum). Il y a eu beaucoup de bons travaux récents sur les graphes planaires utilisant des séparateurs - ce serait bien d'avoir un bon aperçu de ce genre de choses ...
Sariel Har-Peled