Linear layouts of weakly triangulated graphs
Pourquoi ce travail est dans la base
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Notice bibliographique
Résumé
A graph [Formula: see text] is said to be triangulated if it has no chordless cycles of length 4 or more. Such a graph is said to be rigid if, for a valid assignment of edge lengths, it has a unique linear layout and non-rigid otherwise. Damaschke [Point placement on the line by distance data, Discrete Appl. Math. 127(1) (2003) 53–62] showed how to compute all linear layouts of a triangulated graph, for a valid assignment of lengths to the edges of [Formula: see text]. In this paper, we extend this result to weakly triangulated graphs, resolving an open problem. A weakly triangulated graph can be constructively characterized by a peripheral ordering of its edges. The main contribution of this paper is to exploit such an edge order to identify the rigid and non-rigid components of [Formula: see text]. We first show that a weakly triangulated graph without articulation points has at most [Formula: see text] different linear layouts, where [Formula: see text] is the number of quadrilaterals (4-cycles) in [Formula: see text]. When [Formula: see text] has articulation points, the number of linear layouts is at most [Formula: see text], where [Formula: see text] is the number of nodes in the block tree of [Formula: see text] and [Formula: see text] is the total number of quadrilaterals over all the blocks. Finally, we propose an algorithm for computing a peripheral edge order of [Formula: see text] by exploiting an interesting connection between this problem and the problem of identifying a two-pair in [Formula: see text]. Using an [Formula: see text] time solution for the latter problem, we propose an [Formula: see text] time algorithm for computing its peripheral edge order, where [Formula: see text] and [Formula: see text] are respectively the number of edges and vertices of [Formula: see text]. For sparse graphs, the time complexity can be improved to [Formula: see text], using the concept of handles [R. B. Hayward, J. P. Spinrad and R. Sritharan, Improved algorithms for weakly chordal graphs, ACM Trans. Algorithms 3(2) (2007) 19pp].
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.
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,000 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,000 |
| Études des sciences et des technologies | 0,000 | 0,000 |
| Communication savante | 0,000 | 0,000 |
| Science ouverte | 0,000 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,000 | 0,000 |
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écoule