Tree decompositions and linear time algorithms
Bibliographic record
Abstract
This thesis concerns tree decompositions.Trees are one of the simplest and most well understood class of graphs.A tree decomposition of a graph improves our understanding of the graph in a similar way.For example, as a consequence of Robertson and Seymour's groundbreaking work in the theory of graph minors, there are linear time algorithms for NP-hard problem on graphs that admit a tree decomposition of a certain type.We classify existing tree decompositions and examine what makes a tree decomposition unique.The first result of this thesis is a linear time algorithm for building a tree decomposition for the class of graphs that exclude K 5 as a minor.The second result is a significant modification to this algorithm which results in a linear time algorithm to construct the tree decomposition for graphs which exclude a special set of paths.These are vertex disjoint paths between two pairs of input vertices (s 1 , t 1 ), (s 2 , t 2 ), one from s 1 to t 1 and the other from s 2 to t 2 .We then use these tree decompositions to improve the running time of existing algorithms and extend the allowed input of other algorithms from planar graphs to graphs that exclude K 5 as a minor.v ABR G Cette thse traite de dcompositions arborescentes.Les arbres font partie des classes de graphes les mieux comprises.La dcomposition arborescente d'un graphe amliore notre comprhension de ce dernier.Par exemple, grce aux travaux de Robertson et Seymour sur les mineurs d'un graphe, nous savons qu'il existe, pour des problmes qui sont en gnral NP-difficiles, un algorithme linaire pour les graphes admettant une certaine dcomposition arborescente.Nous classons les dcompositions arborescentes connues et dterminons les propits qui rendent cette dcomposition unique.Comme premier rsultat, nous donnons un algorithme linaire pour construire une dcomposition arborescente d'un graphe sans mineur du graphe complet K 5 .Notre deuxime resultat repose sur une modification de cet algorithme afin d'obtenir un autre algorithme linaire.Ce dernier permet la construction d'une dcomposition arborescente d'un graphe qui ne contient pas deux chemins sommets disjoints entre deux paires de sommets donnes (s 1 , t 1 ) et (s 2 , t 2 ).Nous utilisons ces deux dcompositions pour amliorer le temps de calcul des algorithmes existants et modifions des algorithmes pour graphes planaires pour leur permettre de prendre comme donne des graphes sans mineur K 5 .vi
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.000 | 0.000 |
| Meta-epidemiology (narrow) | 0.001 | 0.001 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.001 | 0.000 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.001 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".