BOUNDED LENGTH, 2-EDGE AUGMENTATION OF GEOMETRIC PLANAR GRAPHS
Notice bibliographique
Résumé
2-Edge connectivity is an important fault tolerance property of a network because it maintains network communication despite the deletion of a single arbitrary edge. Planar spanning subgraphs have been shown to play a significant role for achieving local decentralized routing in wireless networks. Existing algorithmic constructions of spanning planar subgraphs of unit disk graphs (UDGs) such as Minimum Spanning Tree, Gabriel Graph, Nearest Neighborhood Graph, etc. do not always ensure connectivity of the resulting graph under single edge deletion. Furthermore, adding edges to the network so as to improve its edge connectivity not only may create edge crossings (at points which are not vertices) but it may also require edges of unbounded length. Thus we are faced with the problem of constructing 2-edge connected geometric planar spanning graphs by adding edges of bounded length without creating edge crossings (at points which are not vertices). To overcome this difficulty, in this paper we address the problem of augmenting the edge set (i.e., adding new edges) of planar geometric graphs with straight line edges of bounded length so that the resulting graph is planar and 2-edge connected. We provide bounds on the number of newly added straight-line edges, prove that such edges can be of length at most 3 times the max length of an edge of the original graph, and also show that the factor 3 is optimal. It is shown to be NP-Complete to augment a geometric planar graph to a 2-edge connected geometric planar graph with the minimum number of new edges of a given bounded length. We also provide a constant time algorithm that works in location-aware settings to augment a planar graph into a 2-edge connected planar graph with straight-line edges of length bounded by 3 times the longest edge of the original graph. It turns out that knowledge of vertex coordinates is crucial to our construction and in fact we prove that this problem cannot be solved locally if the vertices do not know their coordinates. Moreover, we provide a family of k-connected UDGs which does not have 2-edge connected spanning planar subgraphs, for any [Formula: see text].
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,000 | 0,004 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,000 | 0,001 |
| Bibliométrie | 0,001 | 0,001 |
| Études des sciences et des technologies | 0,001 | 0,001 |
| Communication savante | 0,001 | 0,002 |
| Science ouverte | 0,001 | 0,002 |
| Intégrité de la recherche | 0,001 | 0,001 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,002 | 0,001 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule source (Gemma direct ou Codex distillé), pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».