L'existence d'un préservateur de distance planaire?

14

Soit G un graphe non orienté à n nœuds, et soit T un sous-ensemble de nœuds de V (G) appelés terminaux . Un conservateur de distance de (G, T) est un graphe H satisfaisant la propriété

H(u,v)=g(u,v)

pour tous les nœuds u, v dans T. (Notez que H n'est PAS nécessairement un sous-graphe de G.)

Par exemple, soit G le graphe suivant (a) et T les nœuds sur la face externe. Le graphe (b) est alors un conservateur de distance de (G, T).

entrez la description de l'image ici

Il existe une préservation de la distance avec divers paramètres. Je suis particulièrement intéressé par celui avec les propriétés suivantes:

  1. G est plan et non pondéré (c'est-à-dire que toutes les arêtes de G ont un poids),
  2. T a la taille O(n0,5) , et
  3. H a la taille (le nombre de nœuds et d'arêtes) . (Ce serait bien si nous avions O ( no(n).)O(nJournalJournaln)

Existe-t-il un tel conservateur de distance?

Si l'on ne peut pas rencontrer les propriétés ci-dessus, tout type de détente est le bienvenu.


Les références:

Le conservateur de distance est également connu comme un émulateur ; de nombreux travaux connexes peuvent être trouvés sur Internet en recherchant le terme clé , qui nécessite que H soit un sous-graphique de G. Mais dans mes applications, nous pouvons également utiliser d'autres graphiques, tant que H préserve les distances entre T dans G.

Hsien-Chih Chang 張顯 之
la source
-1 pour utiliser JPEG pour ce genre de figure! (je plaisante, mais le PNG est généralement bien meilleur en termes de qualité d'image et de taille de fichier pour les chiffres simples)
Tsuyoshi Ito
@Tsuyoshi: Merci pour les conseils utiles! Je ne le savais pas :)
Hsien-Chih Chang 張顯 之

Réponses:

4

De nombreuses années plus tard, il semble qu'OP ait finalement répondu à sa propre question: émulateur de distance quasi-optimal pour les graphiques planaires par Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes et Oren Weimann vient d'être publié sur l'arxiv.

O~(min{t2,tn})|T|=:tO~(n3/4)O~(n)

(Sur une note moins formelle, je trouve ce résultat vraiment incroyable. Félicitations!)

GMB
la source
1
Merci @GMB de l'avoir posté comme réponse. Un petit hic ici est que le conservateur est dirigé ; il s'agit de savoir s'il existe un émulateur non dirigé (mais toujours pas nécessairement plan) de taille sublinéaire. Mais c'est assez satisfaisant de connaître enfin la réponse à une vieille question après toutes ces années :)
Hsien-Chih Chang 張顯 之
2

vous voudrez peut-être regarder la clé de sous-ensemble planaire de Klein, qui préserve les distances jusqu'à un facteur 1 + epsilon.

Une clé de sous-ensemble pour les graphiques planaires, avec application au sous-ensemble TSP http://doi.acm.org/10.1145/1132516.1132620

Christian Sommer
la source
Merci, j'ai lu le journal et il y a un écart entre sa construction et nos exigences. Il semble que toute clé ne fonctionnera pas tant qu'il s'agit d'un sous-graphique du graphique d'origine; on peut prendre un graphique en grille comme contre-exemple. Mais il existe des émulateurs pour les graphiques en grille.
Hsien-Chih Chang 張顯 之
une autre idée de construction, ça marche peut-être? 1) appliquer récursivement des séparateurs à plus court chemin (Thorup, FOCS'01) 2) eps-cover pour chaque sommet [les deux premières étapes construisent les étiquettes de distance] il y a des terminaux sqrt {n}, chacun avec une étiquette de taille O (log n / eps), se connectant à un nombre total d'au plus sqrt {n} * log n chemins et 1 / eps fois plus de portails 3) raccourci les portails sur les chemins par les bords pondérés et raccourci les connexions aux portails par les bords que le graphique résultant devrait avoir à peu près sqrt {n} * log n sommets et arêtes (jusqu'à eps) et représente 1 + eps les chemins les plus courts pour des distances exactes je ne sais pas ...
Christian Sommer