To see the other types of publications on this topic, follow the link: Tree graphs.
Dissertations / Theses on the topic 'Tree graphs'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Tree graphs.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Mahoney, James Raymond. "Tree Graphs and Orthogonal Spanning Tree Decompositions." PDXScholar, 2016. http://pdxscholar.library.pdx.edu/open_access_etds/2944.
Full textAbstract:
Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.
2
Abu-Ata, Muad Mustafa. "Tree-Like Structure in Graphs and Embedability to Trees." Kent State University / OhioLINK, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=kent1397345185.
Full text
3
Besomi, Ormazábal Guido Andrés. "Tree embeddings in dense graphs." Tesis, Universidad de Chile, 2018. http://repositorio.uchile.cl/handle/2250/164009.
Full textAbstract:
Magíster en Ciencias de la Ingeniería, Mención Matemáticas AplicadasMemoria para optar al título de Ingeniero Civil Matemático
En 1995 Komlós, Sárközy y Szemerédi probaron que para cualquier $\delta>0$ y cualquier entero positivo $\Delta$, todo grafo $G$ de orden $n$, con $n$ suficientemente grande, que satisfaga $\delta(G)\geq (1+\delta)\frac{n}{2}$, contiene como subgrafo a todo árbol de $n$ vértices y grado máximo acotado por $\Delta$. En esta memoria se presentan dos posibles generalizaciones de este resultado, estableciendo condiciones suficientes para el \textit{embedding} de árboles de orden $k$ en grafos con grado mínimo al menos $(1+\delta)\frac{k}{2}$, donde $k$ es lineal en el orden del grafo anfitrión. En 1963 Erd\H{o}s y Sós conjeturaron que, dado un entero $k$, un grafo $G$ con grado promedio mayor que $k-1$ debería contener todos los árboles en $k$ aristas como subgrafos. Como consecuencia de uno de los resultados principales de esta memoria, se demuestra una versión parcial de la conjetura de Erd\H{o}s-Sós. Siguiendo la linea del \textit{embedding} de árboles en grafos con condiciones de grado mínimo, Havet, Reed, Stein y Wood conjeturaron el 2016 que todo grafo con grado mínimo al menos $\lfloor\frac{2k}{3}\rfloor$ y grado máximo al menos $k$ contiene todo árbol con $k$ aristas como subgrafo. Las técnicas aquí desarrolladas permiten, adicionalmente, probar una versión parcial de esta conjetura.
CMM - Conicyt PIA AFB170001
4
Naveed, Ahmed Azam. "On Enumeration of Tree-Like Graphs and Pairwise Compatibility Graphs." Doctoral thesis, Kyoto University, 2021. http://hdl.handle.net/2433/263783.
Full text
5
Tarrés, Puertas Marta Isabel. "Direct tree decomposition of geometric constraint graphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2014. http://hdl.handle.net/10803/285011.
Full textAbstract:
The evolution of constraint based geometric models is tightly tied to parametric and feature-based Computer-Aided Design (CAD) systems. Since the introduction of parametric design by Pro/Engineer in the 1980's, most major CAD systems adopted constraint based geometric models as a core technology. Constraint based geometric models allowed CAD systems to provide a more powerful data model while offering an intuitive user interface. Later on, the same models also found application to fields like linkage design, chemical modeling, computer vision and dynamic geometry.
Constraint based geometric models are unevaluated models. A key problem related to constraint based geometric models is the geometric constraint based solving problem which, roughly speaking, can be stated as the problem of evaluating a constraint based model. Among the different approaches to geometric constraint solving, we are interested in graph-based Decomposition-Recombination solvers. In the graph-based constructive approach, the geometric problem is first translated into a graph whose vertices represent the set of geometric elements and whose edges are the constraints. Then the constraint problem is solved by decomposing the graph into a set of sub-problems, each sub-problem is recursively divided until reaching basic problems which are solved by a dedicated equational solver. The solution to the initial problem is computed by merging the solutions to the sub-problems.
The approach used by DR-solvers has been particularly successful when the decomposition into subproblems and subsequent recombination of solutions to these subproblems can be described by a plan generated a priori, that is, a plan generated as a preprocessing step without actually solving the subsystems. The plan output by the DR-planner remains unchanged as numerical values of parameters change. Such a plan is known as a DR-plan and the unit in the solver that generates it is the DR-planner. In this setting, the DR-plan is then used to drive the actual solving process, that is, computing specific coordinates that properly place geometric objects with respect to each other.
In this thesis we develop a new DR-planner algorithm for graph-constructive two dimensional DR-solvers. This DR-planner is based on the tree-decomposition of a graph. The triangle- or tree-decomposition of a graph decomposes a graph into three subgraphs such that subgraphs pairwise share one vertex. Shared vertices are called hinges. The tree-decomposition of a geometric constraint graph is in some sense the construction plan that solves the corresponding problem. The DR-planner algorithm first transforms the input graph into a simpler, planar graph. After that, an specific planar embedding is computed for the transformed graph where hinges, if any, can be straightly found. In the work we proof the soundness of the new algorithm. We also show that the worst case time performance of the resthe number of vertices of the input graph. The resulting algorithm is easy to implement and is as efficient as other known solving algorithms.L'evolució de models geomètrics basats en restriccions està fortament lligada al sistemes de Disseny Assistit per Computador (CAD) paramètrics i als basats en el paradigma de disseny per mitjà de característiques. Des de la introducció del disseny paramètric per part de Pro/Engineer en els anys 80, la major part de sistemes CAD utilitzaren com a tecnologia de base els models geomètrics basats en restriccions. Els models geomètrics basats en restriccions permeteren als sistemes CAD proporcionar un model d'informació més ampli i alhora oferir una interfície d'usuari intuitiva. Posteriorment, els mateixos models s'aplicaren en camps com el disseny de mecanismes, el modelatge químic, la visió per computador i la geometria dinàmica. Els models geomètrics basats en restriccions són models no avaluats. Un problema clau relacionat amb el models de restriccions geomètriques és el problema de la resolució de restriccions geomètriques, que es resumeix com el problema d'avaluar un model basat en restriccions. Entre els diferents enfocs de resolució de restriccions geomètriques, tractem els solvers de Descomposició-Recombinació (DR-solvers) basats en graphs. En l'enfoc constructiu basat en grafs, el problema geomètric es trasllada en un pas inicial a un graf, on els vèrtexs del graf representen el conjunt d'elements geomètrics i on les arestes corresponen a les restriccions geomètriques entre els elements. A continuació el problema de restriccions es resol descomposant el graf en un conjunt de subproblemes, cadascun dels quals es divideix recursivament fins a obtenir problemes bàsics, que sovint són operacions geomètriques realitzables, per exemple, amb regle i compàs, i que es resolen per mitjà d'un solver numèric específic. Finalment, la solució del problema inicial s'obté recombinant les solucions dels subproblemes. L'enfoc utilitzat pels DR-solvers ha esdevingut especialment interessant quan la descomposició en subproblemes i la posterior recombinació de solucions d'aquests subproblemes es pot descriure com un pla de construcció generat a priori, és a dir, un pla generat com a pas de pre-procés sense necessitat de resoldre realment els subsistemes. El pla generat pel DR-planner esdevé inalterable encara que els valors numèrics dels paràmetres canviin. Aquest pla es coneix com a DR-plan i la unitat en el solver que el genera és l'anomenat DR-planner. En aquest context, el DR-plan s'utilitza com a eina del procés de resolució en curs, és a dir, permet calcular les coordenades específiques que correctament posicionen els elements geomètrics uns respecte els altres. En aquesta tesi desenvolupem un nou algoritme que és la base del DR-planner per a DR-solvers constructius basats en grafs en l'espai bidimensional. Aquest DR-planner es basa en la descomposició en arbre d'un graf. La descomposició en triangles o arbre de descomposició d'un graf es basa en descomposar un graf en tres subgrafs tals que comparteixen un vèrtex 2 a 2. El conjunt de vèrtexs compartits s'anomenen \emph{hinges}. La descomposició en arbre d'un graf de restriccions geomètriques equival, en cert sentit, a resoldre el problema de restriccions geomètriques. L'algoritme del DR-planner en primer lloc transforma el graf proporcionat en un graf més simple i planar. A continuació, es calcula el dibuix en el pla del graf transformat, on les hinges, si n'hi ha, es calculen de manera directa. En aquest treball demostrem la correctesa del nou algoritme. Finalment, proporcionem l'estudi de la complexitat temporal de l'algoritme en cas pitjor i demostrem que és quadràtica en el nombre de vèrtexs del graf proporcionat. L'algoritme resultant és senzill d'implementar i tan eficient com altres algoritmes de resolució concrets
6
Rhodes, Benjamin Robert. "On the Discrete Number of Tree Graphs." Thesis, Virginia Tech, 2020. http://hdl.handle.net/10919/98536.
Full textAbstract:
We study a generalization of the problem of finding bounds on the number of discrete chains, which itself is a generalization of the Erdős unit distance problem. Given a set of points in Euclidean space and a tree graph consisting of a much smaller number of vertices, we study the maximum possible number of tree graphs which can be represented by a prescribed tree graph. We derive an algorithm for finding tight bounds for this family of problems up to chain bound discrepancy, and give upper and lower bounds in special cases.Master of Science
We study a generalization of the problem of finding bounds on the number of discrete chains, which itself is a generalization of the Erdős unit distance problem, a famous mathematics problem named after mathematician Paul Erdős. Given a set of points, and a tree graph of a much smaller amount of vertices, we study the maximum possible number of tree graphs which can be represented by a prescribed tree graph. We derive an algorithm for finding tight bounds for this family of problems up to chain bound discrepancy, and give upper and lower bounds in special cases.
7
Broutin, Nicolas. "Random trees, graphs and recursive partitions." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00842019.
Full textAbstract:
Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:Arbres aléatoires uniformes. Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.
Graphes aléatoires. J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. Arbres couvrant minimaux. J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.
8
Leitert, Arne. "Tree-Breadth of Graphs with Variants and Applications." Kent State University / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=kent1497402176814598.
Full text
9
Bertacchi, D., and Andreas Cap@esi ac at. "Random Walks on Diestel--Leader Graphs." ESI preprints, 2001. ftp://ftp.esi.ac.at/pub/Preprints/esi1004.ps.
Full text
10
Sanders, Daniel Preston. "Linear algorithms for graphs of tree-width at most four." Diss., Georgia Institute of Technology, 1993. http://hdl.handle.net/1853/30061.
Full text
11
Zhao, Yang. "Computational Methods for Analyzing Chemical Graphs and Biological Networks." 京都大学 (Kyoto University), 2014. http://hdl.handle.net/2433/188864.
Full text
12
Carmesin, Johannes [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "Tree-decompositions of finite and infinite graphs / Johannes Carmesin. Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2016. http://d-nb.info/1100160116/34.
Full text
13
Hamann, Matthias [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "Infinite graphs with a tree-like structure / Matthias Hamann. Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2011. http://d-nb.info/1020417390/34.
Full text
14
Song, Lanzhen. "On the independence polynomials of k-tree related and well-covered graphs /." Full text available from ProQuest UM Digital Dissertations, 2009. http://0-proquest.umi.com.umiss.lib.olemiss.edu/pqdweb?index=0&did=1800301781&SrchMode=1&sid=11&Fmt=2&VInst=PROD&VType=PQD&RQT=309&VName=PQD&TS=1268681953&clientId=22256.
Full text
15
Powell, Tracy. "The Singular Values of the Exponientiated Adjacency Matrixes of Broom-Tree Graphs." Scholarship @ Claremont, 2006. https://scholarship.claremont.edu/hmc_theses/186.
Full textAbstract:
In this paper, we explore the singular values of adjacency matrices {An} for a particular family {Gn} of graphs, known as broom trees. The singular values of a matrix M are defined to be the square roots of the eigenvalues of the symmetrized matrix MTM. The matrices we are interested in are the symmetrized adjacency matrices AnTAn and the symmetrized exponentiated adjacency matrices BnTBn = (eAn − I)T(eAn − I) of the graphs Gn. The application of these matrices in the HITS algorithm for Internet searches suggests that we study whether the largest two eigenvalues of AnTAn (or those of BnTBn) can become close or in fact coincide. We have shown that for one family of broom-trees, the ratio of the two largest eigenvalues of BnTBn as the number n of nodes (more specifically, the length l of the graph) goes to infinity is bounded below one. This bound shows that for these graphs, the second largest eigenvalue remains bounded away from the largest eigenvalue. For a second family of broom trees it is not known whether the same is true. However, we have shown that for that family a certain later eigenvalue remains bounded away from the largest eigenvalue. Our last result is a generalization of this latter result.
16
Law, Hiu-Fai. "Trees and graphs : congestion, polynomials and reconstruction." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:54190b51-cd9d-489e-a79e-82ecdf15b4c5.
Full textAbstract:
Spanning tree congestion was defined by Ostrovskii (2004) as a measure of how well a network can perform if only minimal connection can be maintained. We compute the parameter for several families of graphs. In particular, by partitioning a hypercube into pieces with almost optimal edge-boundaries, we give tight estimates of the parameter thereby disproving a conjecture of Hruska (2008). For a typical random graph, the parameter exhibits a zigzag behaviour reflecting the feature that it is not monotone in the number of edges. This motivates the study of the most congested graphs where we show that any graph is close to a graph with small congestion. Next, we enumerate independent sets. Using the independent set polynomial, we compute the extrema of averages in trees and graphs. Furthermore, we consider inverse problems among trees and resolve a conjecture of Wagner (2009). A result in a more general setting is also proved which answers a question of Alon, Haber and Krivelevich (2011). After briefly considering polynomial invariants of general graphs, we specialize into trees. Three levels of tree distinguishing power are exhibited. We show that polynomials which do not distinguish rooted trees define typically exponentially large equivalence classes. On the other hand, we prove that the rooted Ising polynomial distinguishes rooted trees and that the Negami polynomial determines the subtree polynomial, strengthening results of Bollobás and Riordan (2000) and Martin, Morin and Wagner (2008). The top level consists of the chromatic symmetric function and it is proved to be a complete invariant for caterpillars.
17
Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.
Full textAbstract:
In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
18
Zelke, Mariano. "Algorithms for streaming graphs." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, 2009. http://dx.doi.org/10.18452/15912.
Full textAbstract:
Für einen Algorithmus zum Lösen eines Graphenproblems wird üblicherweise angenommen, dieser sei mit wahlfreiem Zugriff (random access) auf den Eingabegraphen G ausgestattet, als auch mit einem Arbeitsspeicher, der G vollständig aufzunehmen vermag. Diese Annahmen erweisen sich als fragwürdig, wenn Graphen betrachtet werden, deren Größe jene konventioneller Arbeitsspeicher übersteigt. Solche Graphen können nur auf externen Speichern wie Festplatten oder Magnetbändern vorrätig gehalten werden, auf denen wahlfreier Zugriff sehr zeitaufwändig ist. Um riesige Graphen zu bearbeiten, die auf externen Speichern liegen, hat Muthukrishnan 2003 das Modell eines Semi-Streaming Algorithmus vorgeschlagen. Dieses Modell beschränkt die Größe des Arbeitsspeichers und verbietet den wahlfreien Zugriff auf den Eingabegraphen G. Im Gegenteil wird angenommen, die Eingabe sei ein Datenstrom bestehend aus Kanten von G in beliebiger Reihenfolge. In der vorliegenden Dissertation entwickeln wir Algorithmen im Semi-Streaming Modell für verschiedene Graphenprobleme. Für das Testen des Zusammenhangs und der Bipartität eines Graphen, als auch für die Berechnung eines minimal spannenden Baumes stellen wir Algorithmen vor, die asymptotisch optimale Laufzeiten erreichen. Es ist bekannt, dass kein Semi-Streaming Algorithmus existieren kann, der ein größtes gewichtetes Matching in einem Graphen findet. Für dieses Problem geben wir den besten bekannten Approximationsalgorithmus an. Schließlich zeigen wir, dass sowohl ein minimaler als auch ein maximaler Schnitt in einem Graphen nicht von einem Semi-Streaming Algorithmus berechnet werden kann. Für beide Probleme stellen wir randomisierte Approximationsalgorithmen im Semi-Streaming Modell vor.An algorithm solving a graph problem is usually expected to have fast random access to the input graph G and a working memory that is able to store G completely. These powerful assumptions are put in question by massive graphs that exceed common working memories and that can only be stored on disks or even tapes. Here, random access is very time-consuming. To tackle massive graphs stored on external memories, Muthukrishnan proposed the semi-streaming model in 2003. It permits a working memory of restricted size and forbids random access to the input graph. In contrast, the input is assumed to be a stream of edges in arbitrary order. In this thesis we develop algorithms in the semi-streaming model approaching different graph problems. For the problems of testing graph connectivity and bipartiteness and for the computation of a minimum spanning tree, we show how to obtain running times that are asymptotically optimal. For the problem of finding a maximum weighted matching, which is known to be intractable in the semi-streaming model, we present the best known approximation algorithm. Finally, we show the minimum and the maximum cut problem in a graph both to be intractable in the semi-streaming model and give semi-streaming algorithms that approximate respective solutions in a randomized fashion.
19
Inkmann, Torsten. "Tree-based decompositions of graphs on surfaces and applications to the traveling salesman problem." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/22583.
Full textAbstract:
Thesis (Ph. D.)--Mathematics, Georgia Institute of Technology, 2008.Committee Chair: Thomas, Robin; Committee Co-Chair: Cook, William J.; Committee Member: Dvorak, Zdenek; Committee Member: Parker, Robert G.; Committee Member: Yu, Xingxing.
20
Mortada, Maidoun. "The b-chromatic number of regular graphs." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10116.
Full textAbstract:
Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que la conjecture d'El Sahili et de Kouider est vraie pour d ≤ 6. En outre, la question a été résolue pour les graphes d-réguliers dans des conditions supplémentaires. Nous étudions la conjecture d'El Sahili et de Kouider en déterminant quand elle est possible et dans quelles conditions supplémentaires elle est vrai. Nous montrons que b(G) = d + 1 si G est un graphe d-régulier qui ne contient pas un cycle d'ordre 4 ni d'ordre 6. En outre, nous fournissons des conditions sur les sommets d'un graphe d-régulier G sans le cycle d'ordre 4 de sorte que b(G) = d + 1. Cabello et Jakovac ont prouvé si v(G) ≥ 2d3 - d2 + d, puis b(G) = d + 1, où G est un graphe d-régulier. Nous améliorons ce résultat en montrant que si v(G) ≥ 2d3 - 2d2 + 2d alors b(G) = d + 1 pour un graphe d-régulier G. 2. Emballage de graphe problème : Soit G un graphe d'ordre n. Considérer une permutation σ : V (G) → V (Kn), la fonction σ* : E(G) → E(Kn) telle que σ *(xy) = σ *(x) σ *(y) est la fonction induite par σ. Nous disons qu'il y a un emballage de k copies de G (dans le graphe complet Kn) s'il existe k permutations σi : V (G) → V (Kn), où i = 1, …, k, telles que σi*(E(G)) ∩ σj (E(G)) = ɸ pour i ≠ j. Un emballage de k copies d'un graphe G est appelé un k-placement de G. La puissance k d'un graphe G, noté par Gk, est un graphe avec le même ensemble de sommets que G et une arête entre deux sommets si et seulement si le distance entre ces deux sommets est au plus k. Kheddouci et al. ont prouvé que pour un arbre non-étoile T, il existe un 2-placement σ sur V (T). Nous introduisons pour la première fois le problème emballage marqué de graphe dans son graphe puissanceTwo problems are considered in this thesis: the b-coloring problem and the graph packing problem. 1. The b-Coloring Problem : A b-coloring of a graph G is a proper coloring of the vertices of G such that there exists a vertex in each color class joined to at least a vertex in each other color class. The b-chromatic number of a graph G, denoted by b(G), is the maximum number t such that G admits a b-coloring with t colors. El Sahili and Kouider asked whether it is true that every d-regular graph G with girth at least 5 satisfies b(G) = d + 1. Blidia, Maffray and Zemir proved that the conjecture is true for d ≤ 6. Also, the question was solved for d-regular graphs with supplementary conditions. We study El Sahili and Kouider conjecture by determining when it is possible and under what supplementary conditions it is true. We prove that b(G) = d+1 if G is a d-regular graph containing neither a cycle of order 4 nor of order 6. Then, we provide specific conditions on the vertices of a d-regular graph G with no cycle of order 4 so that b(G) = d + 1. Cabello and Jakovac proved that if v(G) ≥ 2d3 - d2 + d, then b(G) = d + 1, where G is a d-regular graph. We improve this bound by proving that if v(G) ≥ 2d3 - 2d2 + 2d, then b(G) = d+1 for a d-regular graph G. 2. Graph Packing Problem : Graph packing problem is a classical problem in graph theory and has been extensively studied since the early 70's. Consider a permutation σ : V (G) → V (Kn), the function σ* : E(G) → E(Kn) such that σ *(xy) = σ *(x) σ *(y) is the function induced by σ. We say that there is a packing of k copies of G into the complete graph Kn if there exist k permutations σ i : V (G) → V (Kn), where i = 1,…, k, such that σ*i (E(G)) ∩ σ*j (E(G)) = ɸ for I ≠ j. A packing of k copies of a graph G will be called a k-placement of G. The kth power Gk of a graph G is the supergraph of G formed by adding an edge between all pairs of vertices of G with distance at most k. Kheddouci et al. proved that for any non-star tree T there exists a 2-placement σ on V (T). We introduce a new variant of graph packing problem, called the labeled packing of a graph into its power graph
21
Jonsson, Jakob. "Simplicial Complexes of Graphs." Doctoral thesis, Stockholm, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-202.
Full text
22
Hundertmark, Fabian [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "The tree-like connectivity structure of finite graphs and matroids / Fabian Hundertmark. Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2013. http://d-nb.info/1034421018/34.
Full text
23
Gollin, Jochen Pascal [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "Connectivity and tree structure in infinite graphs and digraphs / Jochen Pascal Gollin ; Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2019. http://d-nb.info/1192913124/34.
Full text
24
Gollin, Jochen Pascal Verfasser], and Reinhard [Akademischer Betreuer] [Diestel. "Connectivity and tree structure in infinite graphs and digraphs / Jochen Pascal Gollin ; Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2019. http://nbn-resolving.de/urn:nbn:de:gbv:18-99171.
Full text
25
Biyikoglu, Türker, and Josef Leydold. "Graphs with given degree sequence and maximal spectral radius." Department of Statistics and Mathematics, WU Vienna University of Economics and Business, 2008. http://epub.wu.ac.at/1160/1/document.pdf.
Full textAbstract:
We describe the structure of those graphs that have largest spectral radius in the class of all connected graphs with a given degree sequence. We show that in such a graph the degree sequence is non-increasing with respect to an ordering of the vertices induced by breadth-first search. For trees the resulting structure is uniquely determined up to isomorphism. We also show that the largest spectral radius in such classes of trees is strictly monotone with respect to majorization. This paper is the revised final version of the preprint no. 35 of this research report series. (author´s abstract)Series: Research Report Series / Department of Statistics and Mathematics
26
Gabrysch, Katja. "On Directed Random Graphs and Greedy Walks on Point Processes." Doctoral thesis, Uppsala universitet, Analys och sannolikhetsteori, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-305859.
Full textAbstract:
This thesis consists of an introduction and five papers, of which two contribute to the theory of directed random graphs and three to the theory of greedy walks on point processes. We consider a directed random graph on a partially ordered vertex set, with an edge between any two comparable vertices present with probability p, independently of all other edges, and each edge is directed from the vertex with smaller label to the vertex with larger label. In Paper I we consider a directed random graph on ℤ2 with the vertices ordered according to the product order and we show that the limiting distribution of the centered and rescaled length of the longest path from (0,0) to (n, [na] ), a<3/14, is the Tracy-Widom distribution. In Paper II we show that, under a suitable rescaling, the closure of vertex 0 of a directed random graph on ℤ with edge probability n−1 converges in distribution to the Poisson-weighted infinite tree. Moreover, we derive limit theorems for the length of the longest path of the Poisson-weighted infinite tree. The greedy walk is a deterministic walk on a point process that always moves from its current position to the nearest not yet visited point. Since the greedy walk on a homogeneous Poisson process on the real line, starting from 0, almost surely does not visit all points, in Paper III we find the distribution of the number of visited points on the negative half-line and the distribution of the index at which the walk achieves its minimum. In Paper IV we place homogeneous Poisson processes first on two intersecting lines and then on two parallel lines and we study whether the greedy walk visits all points of the processes. In Paper V we consider the greedy walk on an inhomogeneous Poisson process on the real line and we determine sufficient and necessary conditions on the mean measure of the process for the walk to visit all points.
27
Moragas, Vilarnau Jordi. "Graph labelings and decompositions by partitioning sets of integers." Doctoral thesis, Universitat Politècnica de Catalunya, 2010. http://hdl.handle.net/10803/5859.
Full textAbstract:
Aquest treball és una contribució a l'estudi de diferents problemes que sorgeixen de dues àrees fortament connexes de la Teoria de Grafs: etiquetaments i descomposicions. Molts etiquetaments de grafs deuen el seu origen als presentats l'any 1967 per Rosa. Un d'aquests etiquetaments, àmpliament conegut com a etiquetament graceful, va ser definit originalment com a eina per atacar la conjectura de Ringel, la qual diu que el graf complet d'ordre 2m+1 pot ser descompost en m copies d'un arbre donat de mida m. Aquí, estudiem etiquetaments relacionats que ens donen certes aproximacions a la conjectura de Ringel, així com també a una altra conjectura de Graham i Häggkvist que, en una forma dèbil, demana la descomposició d'un graf bipartit complet per un arbre donat de mida apropiada. Les principals contribucions que hem fet en aquest tema són la prova de la darrera conjectura per grafs bipartits complets del doble de mida essent descompostos per arbres de gran creixement i un nombre primer d'arestes, i la prova del fet que cada arbre és un subarbre gran de dos arbres pels quals les dues conjectures es compleixen respectivament. Aquests resultats estan principalment basats en una aplicació del mètode polinomial d'Alon.
Un altre tipus d'etiquetaments, els etiquetaments magic, també són tractats aquí. Motivats per la noció de quadrats màgics de Teoria de Nombres, en aquest tipus d'etiquetaments volem asignar nombres enters a parts del graf (vèrtexs, arestes, o vèrtexs i arestes) de manera que la suma de les etiquetes assignades a certes subestructures del graf sigui constant. Desenvolupem tècniques basades en particions de certs conjunts d'enters amb algunes condicions additives per construir etiquetaments cycle-magic, un nou tipus d'etiquetament introduït en aquest treball i que estén la noció clàssica d'etiquetament magic. Els etiquetaments magic no donen cap descomposició de grafs, però les tècniques usades per obtenir-los estan al nucli d'un altre problema de descomposició, l'ascending subgraph decomposition (ASD). Alavi, Boals, Chartrand, Erdös i Oellerman, van conjecturar l'any 1987 que tot graf té un ASD.
Aquí, estudiem l'ASD per grafs bipartits, una classe de grafs per la qual la conjectura encara no ha estat provada. Donem una condició necessària i una de suficient sobre la seqüència de graus d'un estable del graf bipartit de manera que admeti un ASD en que cada factor sigui un star forest. Les tècniques utilitzades estan basades en l'existència de branca-acoloriments en multigrafs bipartits.
També tractem amb el sumset partition problem, motivat per la conjectura ASD, que demana una partició de [n] de manera que la suma dels elements de cada part sigui igual a un valor prescrit. Aquí donem la millor condició possible per la versió modular del problema que ens permet provar els millors resultats ja coneguts en el cas enter per n primer. La prova està de nou basada en el mètode polinomial.
This work is a contribution to the study of various problems that arise from two strongly connected areas of the Graph Theory: graph labelings and graph decompositions. Most graph labelings trace their origins to the ones presented in 1967 by Rosa. One of these labelings, widely known as the graceful labeling, originated as a means of attacking the conjecture of Ringel, which states that the complete graph of order 2m+1 can be decomposed into m copies of a given tree of size m. Here, we study related labelings that give some approaches to Ringel's conjecture, as well as to another conjecture by Graham and Häggkvist that, in a weak form, asks for the decomposition of a complete bipartite graph by a given tree of appropriate size.
Our main contributions in this topic are the proof of the latter conjecture for double sized complete bipartite graphs being decomposed by trees with large growth and prime number of edges, and the proof of the fact that every tree is a large subtree of two trees for which both conjectures hold respectively. These results are mainly based on a novel application of the so-called polynomial method by Alon.
Another kind of labelings, the magic labelings, are also treated. Motivated by the notion of magic squares in Number Theory, in these type of labelings we want to assign integers to the parts of a graph (vertices, edges, or vertices and edges) in such a way that the sums of the labels assigned to certain substructures of the graph remain constant. We develop techniques based on partitions of certain sets of integers with some additive conditions to construct cycle-magic labelings, a new brand introduced in this work that extends the classical magic labelings. Magic labelings do not provide any graph decomposition, but the techniques that we use to obtain them are the core of another decomposition problem, the ascending subgraph decomposition (ASD).
In 1987, was conjectured by Alavi, Boals. Chartrand, Erdös and Oellerman that every graph has an ASD. Here, we study ASD of bipartite graphs, a class of graphs for which the conjecture has not been shown to hold. We give a necessary and a sufficient condition on the one sided degree sequence of a bipartite graph in order that it admits an ASD by star forests. Here the techniques are based on the existence of edge-colorings in bipartite multigraphs.
Motivated by the ASD conjecture we also deal with the sumset partition problem, which asks for a partition of [n] in such a way that the sum of the elements of each part is equal to a prescribed value. We give a best possible condition for the modular version of the sumset partition problem that allows us to prove the best known results in the integer case for n a prime. The proof is again based on the polynomial method.
28
Tan, Kunlun. "On the Role of Partition Inequalities in Classical Algorithms for Steiner Problems in Graphs." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/1123.
Full textAbstract:
The Steiner tree problem is a classical, well-studied, $\mathcal{NP}$-hard optimization problem. Here we are given an undirected graph $G=(V,E)$, a subset $R$ of $V$ of terminals, and non-negative costs $c_e$ for all edges $e$ in $E$. A feasible Steiner tree for a given instance is a tree $T$ in $G$ that spans all terminals in $R$. The goal is to compute a feasible Steiner tree of smallest cost. In this thesis we will focus on approximation algorithms for this problem: a $c$-approximation algorithm is an algorithm that returns a tree of cost at most $c$ times that of an optimum solution for any given input instance. In a series of papers throughout the last decade, the approximation guarantee $c$ for the Steiner tree problem has been improved to the currently best known value of 1. 55 (Robins, Zelikovsky). Robins' and Zelikovsky's algorithm as well as most of its predecessors are greedy algorithms.
Apart from algorithmic improvements, there also has been substantial work on obtaining tight linear-programming relaxations for the Steiner tree problem. Many undirected and directed formulations have been proposed in the course of the last 25 years; their use, however, is to this point mostly restricted to the field of exact optimization. There are few examples of algorithms for the Steiner tree problem that make use of these LP relaxations. The best known such algorithm for general graphs is a 2-approximation (for the more general Steiner forest problem) due to Agrawal, Klein and Ravi. Their analysis is tight as the LP-relaxation used in their work is known to be weak: it has an IP/LP gap of approximately 2.
Most recent efforts to obtain algorithms for the Steiner tree problem that are based on LP-relaxations has focused on directed relaxations. In this thesis we present an undirected relaxation and show that the algorithm of Robins and Zelikovsky returns a Steiner tree whose cost is at most 1. 55 times its optimum solution value. In fact, we show that this algorithm can be viewed as a primal-dual algorithm.
The Steiner forest problem is a generalization of the Steiner tree problem. In the problem, instead of only one set of terminals, we are given more than one terminal set. An feasible Steiner forest is a forest that connects all terminals in the same terminal set for each terminal set. The goal is to find a minimum cost feasible Steiner forest. In this thesis, a new set of facet defining inequalities for the polyhedra of the Steiner forest is introduced.
29
Mirza, Behrouz. "On the transition between crystalline and gravitational phases in two dimensional theories with matter fields." Thesis, University of Oxford, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.318930.
Full text
30
Borozan, Valentin. "Proper and weak-proper trees in edges-colored graphs and multigraphs." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00738959.
Full textAbstract:
Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1.
31
Silva, Ana Shirley Ferreira da. "Um estudo computacional sobre o problema de decomposiÃÃo de grafos em Ãrvore." Universidade Federal do CearÃ, 2005. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=2144.
Full textAbstract:
CoordenaÃÃo de AperfeiÃoamento de NÃvel SuperiorA noÃÃo de DecomposiÃÃo em Ãrvore foi introduzida por Robertson e Seymour em sua sÃrie de artigos sobre menores de grafos e pode ser definida, intuitivamente, como uma organizaÃÃo dos vÃrtices e arestas do grafo em uma estrutura de Ãrvore, sendo a largura da decomposiÃÃo igual ao tamanho do maior subconjunto de vÃrtices relacionado a um nà desta estrutura menos um. A largura mÃnima de uma decomposiÃÃo em Ãrvore de um grafo G à chamada de largura em Ãrvore de G. VÃrios problemas difÃceis podem ser resolvidos em tempo polinomial, dada uma decomposiÃÃo em Ãrvore de largura limitada, como, por exemplo, Ciclo Hamiltoniano, Conjunto Independente MÃximo, Isomorfismo, ColoraÃÃo de VÃrtices, etc. A complexidade dos algoritmos que resolvem tais problemas sÃo geralmente exponenciais na largura da decomposiÃÃo fornecida. Logo, à esperado que encontrar uma decomposiÃÃo de largura mÃnima seja um problema difÃcil. De fato, Arnborg, Corneil e Proskurowski [2] mostraram que o problema à NP - difÃcil. O problema de encontrar a largura em Ãrvore de um grafo qualquer à o objeto de estudo da presente dissertaÃÃo de mestrado. Uma restriÃÃo desse problema à o de decidir, para um inteiro k fixo, se a largura em Ãrvore de G à no mÃximo k. Apresentamos a prova de que o problema para k fixo pode ser resolvido polinomialmente. Na Ãltima dÃcada foram propostas vÃrias heurÃsticas que fornecem limites superiores para o problema [3, 10], heurÃsticas para o cÃlculo de limites inferiores [6, 8, 11], alÃm de mÃtodos enumerativos [5] e algoritmos aproximativos [1, 7, 4]. PorÃm, nenhum resultado obtido pode ser considerado bom, uma vez que nÃo existe um benchmark para o qual se conhece a largura em Ãrvore e os limites inferiores e superiores tÃm se mostrado muito distantes. AlÃm disso, o algoritmo enumerativo existente mostrou-se ineficiente mesmo para o problema de decisÃo com k fixo em valores pequenos (por exemplo, k = 4) [12]. à neste quadro que propomos um mÃtodo enumerativo para o problema. Na verdade, abordamos o problema de triangularizaÃÃo, que à equivalente ao problema de decomposiÃÃo em Ãrvore. Isso nos permitiu a proposta de uma nova representaÃÃo para uma soluÃÃo do problema que utiliza o conceito de ordens totais. Uma vez que as soluÃÃes podem assim ser representadas, um algoritmo que enumere as extensÃes totais de uma dada ordem parcial pode ser utilizado para enumerar todas as soluÃÃes do problema, bastando que fornecemos uma ordem que contenha apenas os pares reflexivos vv, onde v à um vÃrtice do grafo de entrada. O mÃtodo enumerativo proposto à uma modificaÃÃo do algoritmo de CorrÃa e Szwarcfiter [9]. Esta modificaÃÃo faz com que apenas as extensÃes totais da ordem fornecida seja enumerada. O algoritmo apresenta duas principais vantagens com relaÃÃo ao mÃtodo enumerativo proposto por Bodlaender e Kloks: pode ser utilizado juntamente com o mÃtodo âbranch and boundâ; e pode enumerar um sub-espaÃo de soluÃÃes, o que pode ser Ãtil caso se conheÃa algumas relaÃÃes existentes na soluÃÃo Ãtima, ou mesmo para investigar determinados sub-espaÃos de soluÃÃes. Implementamos e testamos o algoritmo proposto, aplicando o mÃtodo âbranch and boundâ e restringindo o espaÃo de soluÃÃes. As ordens parciais utilizadas para definir os sub-espaÃos explorados foram obtidas baseando-se nas heurÃsticas de limite superior que utilizam rotulaÃÃo. Infelizmente, nÃo obtivemos bons resultados, pois, mesmo restringindo o espaÃo de busca, a quantidade de nÃs gerados da Ãrvore de âbranch and boundâ foi muito grande, excedendo a quantidade de memÃria disponÃvel da mÃquina utilizada para os testes. No texto da dissertaÃÃo apresentamos tambÃm um estudo da complexidade do problema, um algoritmo para calcular uma decomposiÃÃo em Ãrvore Ãtima de um grafo cordal, alÃm das vÃrias heurÃsticas para o cÃlculo de limites superiores e inferiores existentes. AlÃm disso, implementamos e testamos as heurÃsticas de limite superior que utilizam rotulaÃÃo e uma heurÃstica GRASP, tendo sido o primeiro estudo de uma aplicaÃÃo da meta-heurÃstica GRASP para o problema de decomposiÃÃo em Ãrvore.
The notion of Tree Decomposition was introduced by Robertson and Seymour in their seris of articles about graph minors and can be intuitively seen as an organization of the vertices and edges of the graph in a tree structure, being the treewidth equal to the size of the largest subset of vertices minus one. The minimum treewidth over all tree decompositions of a graph gives us the treewidth of the graph. Many hard problems can be polinomially solved for a graph G if a tree decomposition with bounded treewidth of G is given. For instance, hamiltonian cycle, maximum independent set isomorphism, vertex coloring, etc. The complexity of the algorithm that solves such problems are generally exponential on the width of the given tree decomposition. So, we can expect that finding a tree decomposition of minimum width is hard. In fact, Arnborg, Corneil and Proskurowski [2] showed that the problem os NP-hard. The problem of finding the treewidth of a graph is the subject of this thesis. The decision variation of the problem is, given a graph G and for a fixed integer k, deciding if the treewidth of G is at most k. We discuss a proof that the decision problem can be polynomially solved. In the last decade were proposed many heuristics for computing upper bounds [3, 10], lower bounds [6, 8, 11], enumeration methods [5] and approximative algorithms [1, 7, 4]. However, none of these results can be considered as good ones, since there is no benchmarks for with the treewidth is known, as well as the difference between the lower and upper bounds for the existing benchmarks is very large. Additionally, the enumeration method was showed to be inefficient even for the decision problem with k fixed in small values (e.g., k = 4) [12]. So, we propose another enumeration method for the problem that can be used along with branch and bound techniques. Actually, we work with the triangulation problem that is equivalent to the tree decomposition problem. We propose a new representation of a solution, wich uses the concept of total orders. Once a solution ca be represented like that, an algorithm that enumerates all the total extensions of a given partial order can be used to enumerate all solutions for the tree decomposition problem, as long as we offer the partial order containing only the reflexive pairs vv, where v is a vertex of the input graph. The proposed enumeration method is a modification of the CorrÃa and Szwarcfiter algorithm [9]. This modification allows only the total extensions to be enumerated. The algorithm presents two principal advantages over the Bodlander and Kloks method: it can be used in conjunction with the Branch and Bound method; and it can enumerate a subspace of solutions, what can be useful if we know some existing relations in an optimal solution, or even to investigate such subspaces in order to characterize them. We have implemented and tested the proposed algorithm, applying the branch and bound method and restricting the subspace of solutions. The partial orders used to define the explored subspaces were obtained based on the labeling heuristics for finding upper bounds. Unfortunately, we did not obtain good results because, even when we restricted the subspace of solutions to be searched, the number of nodes generated in the branch and bound tree was too large, exceeding the machineâs memory capacity. In the text, we also present the proof of the NP-hardness of the problem, an algorithm to compute an optimal decompostion of a chordal graph, and also the many existing heuristics to compute lower and upper bounds. In addition, we implemented and tested the labeling heuristics for upper bounds and a GRASP heuristic, being the first application of a GRASP meta-heuristic to the problem.
32
Harvey, William John. "Understanding High-Dimensional Data Using Reeb Graphs." The Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1342614959.
Full text
33
Warkentin, Matthias. "Exchange Graphs via Quiver Mutation." Doctoral thesis, Universitätsbibliothek Chemnitz, 2014. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-153172.
Full textAbstract:
Inspired by Happel's question, whether the exchange graph and the simplicial complex of tilting modules over a quiver algebra are independent from the multiplicities of multiple arrows in the quiver, we study quantitative aspects of Fomin and Zelevinsky's quiver mutation rule. Our results turn out to be very useful in the mutation-infinite case for understanding combinatorial structures as the cluster exchange graph or the simplicial complex of tilting modules, which are governed by quiver mutation. Using a class of quivers we call forks we can show that any such quiver yields a tree in the exchange graph. This allows us to provide a good global description of the exchange graphs of arbitrary mutation-infinite quivers. In particular we show that the exchange graph of an acyclic quiver is a tree if (and in fact only if) any two vertices are connected by at least two arrows. Furthermore we give classification results for the simplicial complexes and thereby obtain a partial positive answer to Happel's question. Another consequence of our findings is a confirmation of Unger's conjecture about the infinite number of components of the tilting exchange graph in all but finitely many cases. Finally we generalise and conceptualise our results by introducing what we call "polynomial quivers", stating several conjectures about "polynomial quiver mutation", and giving proofs in special cases.
34
Helmberg, Christoph, Israel Rocha, and Uwe Schwerdtfeger. "A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs." Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-175057.
Full textAbstract:
We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.
35
Noble, Steven D. "The complexity of graph polynomials." Thesis, University of Oxford, 1997. http://ora.ox.ac.uk/objects/uuid:c84702b4-b371-474b-a003-4d24f25e5a12.
Full textAbstract:
This thesis examines graph polynomials and particularly their complexity. We give short proofs of two results from Gessel and Sagan (1996) which present new evaluations of the Tutte polynomial concerning orientations. A theorem of Massey et al (1997) gives an expression concerning the average size of a forest in a graph. We generalise this result to any simplicial complex. We answer a question posed by Kleinschmidt and Onn (1995) by showing that the language of partitionable simplicial complexes is in NP. We prove the following result concerning the complexity of the Tutte polynomial: Theorem 1. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers x and y, and evaluate the Tutte polynomial, T(G;x,y). The rank generating function S of a graphic 2-polymatroid was introduced by Oxley and Whittle (1993). It has many similarities to the Tutte polynomial and we prove the following results. Theorem 2. Evaluating S at a fixed point (u,v) is #P-hard unless uv=1 when there is a polynomial time algorithm. Theorem 3. For any fixed k, there exists a polynomial time algorithm A, which will input any graph G, with tree-width at most k, and rational numbers u and v, and evaluate S(G;u,v). We consider a class of graphs $S$, which are those graphs which are obtainable from a graph with no edges using the unsigned version of Reidemeister moves. We examine the relationship between this class and other similarly defined classes such as the delta-wye graphs. There remain many open questions such as whether S contains every graph. However we have an invariant of the moves, based on the Tutte polynomial, which allows us to determine from which graph with no edges, if any, a particular graph can be obtained. Finally we consider a new polynomial on weighted graphs which is motivated by the study of weight systems on chord diagrams. We give three states model and a recipe theorem. An unweighted version of this polynomial is shown to contain as specialisations, a wide range of graph invariants, such as the Tutte polynomial, the polymatroid polynomial of Oxley and Whittle (1993) and the symmetric function generalisation of the chromatic polynomial introduced by Stanley (1995). We close with a discussion of complexity issues proving hardness results for very restricted classes of graphs.
36
Müller, Theodor [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "The excluded minor structure theorem, and linkages in large graphs of bounded tree-width / Theodor Müller. Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2014. http://d-nb.info/1050239148/34.
Full text
37
Müller, Theodor Verfasser], and Reinhard [Akademischer Betreuer] [Diestel. "The excluded minor structure theorem, and linkages in large graphs of bounded tree-width / Theodor Müller. Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2014. http://nbn-resolving.de/urn:nbn:de:gbv:18-67087.
Full text
38
Rinne, Vidar. "A Zoomable 3D User Interface using Uniform Grids and Scene Graphs." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-13360.
Full textAbstract:
Zoomable user interfaces (ZUIs) have been studied for a long time and many applications are built upon them. Most applications, however, only use two dimensions to express the content. This report presents a solution using all three dimensions where the base features are built as a framework with uniform grids and scene graphs as primary data structures. The purpose of these data structures is to improve performance while maintaining flexibility when creating and handling three-dimensional objects. A 3D-ZUI is able to represent the view of the world and its objects in a more lifelike manner. It is possible to interact with the objects much in the same way as in real world. By developing a prototype framework as well as some example applications, the usefulness of 3D-ZUIs is illustrated. Since the framework relies on abstraction and object-oriented principles it is easy to maintain and extend it as needed. The currently implemented data structures are well motivated for a large scale 3D-ZUI in terms of accelerated collision detection and picking and they also provide a flexible base when developing applications. It is possible to further improve performance of the framework, for example by supporting different types of culling and levels of detail
39
Silva, Ana Shirley Ferreira da. "Um estudo computacional sobre o problema de decomposição de grafos em árvore." reponame:Repositório Institucional da UFC, 2005. http://www.repositorio.ufc.br/handle/riufc/16980.
Full textAbstract:
SILVA, Ana Shirley Ferreira da. Um estudo computacional sobre o problema de decomposição de grafos em árvore. 2005. 103 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2005.Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:54:20Z No. of bitstreams: 1 2005_dis_asfsilva.pdf: 965121 bytes, checksum: 0620082b39fd950bff00ce625f59f846 (MD5)
Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-24T19:54:44Z (GMT) No. of bitstreams: 1 2005_dis_asfsilva.pdf: 965121 bytes, checksum: 0620082b39fd950bff00ce625f59f846 (MD5)
Made available in DSpace on 2016-05-24T19:54:44Z (GMT). No. of bitstreams: 1 2005_dis_asfsilva.pdf: 965121 bytes, checksum: 0620082b39fd950bff00ce625f59f846 (MD5) Previous issue date: 2005
The notion of Tree Decomposition was introduced by Robertson and Seymour in their seris of articles about graph minors and can be intuitively seen as an organization of the vertices and edges of the graph in a tree structure, being the treewidth equal to the size of the largest subset of vertices minus one. The minimum treewidth over all tree decompositions of a graph gives us the treewidth of the graph. Many hard problems can be polinomially solved for a graph G if a tree decomposition with bounded treewidth of G is given. For instance, hamiltonian cycle, maximum independent set isomorphism, vertex coloring, etc. The complexity of the algorithm that solves such problems are generally exponential on the width of the given tree decomposition. So, we can expect that finding a tree decomposition of minimum width is hard. In fact, Arnborg, Corneil and Proskurowski [2] showed that the problem os NP-hard. The problem of finding the treewidth of a graph is the subject of this thesis. The decision variation of the problem is, given a graph G and for a fixed integer k, deciding if the treewidth of G is at most k. We discuss a proof that the decision problem can be polynomially solved. In the last decade were proposed many heuristics for computing upper bounds [3, 10], lower bounds [6, 8, 11], enumeration methods [5] and approximative algorithms [1, 7, 4]. However, none of these results can be considered as good ones, since there is no benchmarks for with the treewidth is known, as well as the difference between the lower and upper bounds for the existing benchmarks is very large. Additionally, the enumeration method was showed to be inefficient even for the decision problem with k fixed in small values (e.g., k = 4) [12]. So, we propose another enumeration method for the problem that can be used along with branch and bound techniques. Actually, we work with the triangulation problem that is equivalent to the tree decomposition problem. We propose a new representation of a solution, wich uses the concept of total orders. Once a solution ca be represented like that, an algorithm that enumerates all the total extensions of a given partial order can be used to enumerate all solutions for the tree decomposition problem, as long as we offer the partial order containing only the reflexive pairs vv, where v is a vertex of the input graph. The proposed enumeration method is a modification of the Corrêa and Szwarcfiter algorithm [9]. This modification allows only the total extensions to be enumerated. The algorithm presents two principal advantages over the Bodlander and Kloks method: it can be used in conjunction with the Branch and Bound method; and it can enumerate a subspace of solutions, what can be useful if we know some existing relations in an optimal solution, or even to investigate such subspaces in order to characterize them. We have implemented and tested the proposed algorithm, applying the branch and bound method and restricting the subspace of solutions. The partial orders used to define the explored subspaces were obtained based on the labeling heuristics for finding upper bounds. Unfortunately, we did not obtain good results because, even when we restricted the subspace of solutions to be searched, the number of nodes generated in the branch and bound tree was too large, exceeding the machine’s memory capacity. In the text, we also present the proof of the NP-hardness of the problem, an algorithm to compute an optimal decompostion of a chordal graph, and also the many existing heuristics to compute lower and upper bounds. In addition, we implemented and tested the labeling heuristics for upper bounds and a GRASP heuristic, being the first application of a GRASP meta-heuristic to the problem.
A noção de Decomposição em árvore foi introduzida por Robertson e Seymour em sua série de artigos sobre menores de grafos e pode ser definida, intuitivamente, como uma organização dos vértices e arestas do grafo em uma estrutura de árvore, sendo a largura da decomposição igual ao tamanho do maior subconjunto de vértices relacionado a um nó desta estrutura menos um. A largura mínima de uma decomposição em árvore de um grafo G é chamada de largura em árvore de G. Vários problemas difíceis podem ser resolvidos em tempo polinomial, dada uma decomposição em árvore de largura limitada, como, por exemplo, Ciclo Hamiltoniano, Conjunto Independente Máximo, Isomorfismo, Coloração de Vértices, etc. A complexidade dos algoritmos que resolvem tais problemas são geralmente exponenciais na largura da decomposição fornecida. Logo, é esperado que encontrar uma decomposição de largura mínima seja um problema difícil. De fato, Arnborg, Corneil e Proskurowski [2] mostraram que o problema é NP - difícil. O problema de encontrar a largura em árvore de um grafo qualquer é o objeto de estudo da presente dissertação de mestrado. Uma restrição desse problema é o de decidir, para um inteiro k fixo, se a largura em árvore de G é no máximo k. Apresentamos a prova de que o problema para k fixo pode ser resolvido polinomialmente. Na última década foram propostas várias heurísticas que fornecem limites superiores para o problema [3, 10], heurísticas para o cálculo de limites inferiores [6, 8, 11], além de métodos enumerativos [5] e algoritmos aproximativos [1, 7, 4]. Porém, nenhum resultado obtido pode ser considerado bom, uma vez que não existe um benchmark para o qual se conhece a largura em árvore e os limites inferiores e superiores têm se mostrado muito distantes. Além disso, o algoritmo enumerativo existente mostrou-se ineficiente mesmo para o problema de decisão com k fixo em valores pequenos (por exemplo, k = 4) [12]. É neste quadro que propomos um método enumerativo para o problema. Na verdade, abordamos o problema de triangularização, que é equivalente ao problema de decomposição em árvore. Isso nos permitiu a proposta de uma nova representação para uma solução do problema que utiliza o conceito de ordens totais. Uma vez que as soluções podem assim ser representadas, um algoritmo que enumere as extensões totais de uma dada ordem parcial pode ser utilizado para enumerar todas as soluções do problema, bastando que fornecemos uma ordem que contenha apenas os pares reflexivos vv, onde v é um vértice do grafo de entrada. O método enumerativo proposto é uma modificação do algoritmo de Corrêa e Szwarcfiter [9]. Esta modificação faz com que apenas as extensões totais da ordem fornecida seja enumerada. O algoritmo apresenta duas principais vantagens com relação ao método enumerativo proposto por Bodlaender e Kloks: pode ser utilizado juntamente com o método “branch and bound”; e pode enumerar um sub-espaço de soluções, o que pode ser útil caso se conheça algumas relações existentes na solução ótima, ou mesmo para investigar determinados sub-espaços de soluções. Implementamos e testamos o algoritmo proposto, aplicando o método “branch and bound” e restringindo o espaço de soluções. As ordens parciais utilizadas para definir os sub-espaços explorados foram obtidas baseando-se nas heurísticas de limite superior que utilizam rotulação. Infelizmente, não obtivemos bons resultados, pois, mesmo restringindo o espaço de busca, a quantidade de nós gerados da árvore de “branch and bound” foi muito grande, excedendo a quantidade de memória disponível da máquina utilizada para os testes. No texto da dissertação apresentamos também um estudo da complexidade do problema, um algoritmo para calcular uma decomposição em árvore ótima de um grafo cordal, além das várias heurísticas para o cálculo de limites superiores e inferiores existentes. Além disso, implementamos e testamos as heurísticas de limite superior que utilizam rotulação e uma heurística GRASP, tendo sido o primeiro estudo de uma aplicação da meta-heurística GRASP para o problema de decomposição em árvore.
40
Holmgren, Cecilia. "Split Trees, Cuttings and Explosions." Doctoral thesis, Uppsala universitet, Matematiska institutionen, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-112239.
Full textAbstract:
This thesis is based on four papers investigating properties of split trees and also introducing new methods for studying such trees. Split trees comprise a large class of random trees of logarithmic height and include e.g., binary search trees, m-ary search trees, quadtrees, median of (2k+1)-trees, simplex trees, tries and digital search trees. Split trees are constructed recursively, using “split vectors”, to distribute n “balls” to the vertices/nodes. The vertices of a split tree may contain different numbers of balls; in computer science applications these balls often represent “key numbers”. In the first paper, it was tested whether a recently described method for determining the asymptotic distribution of the number of records (or cuts) in a deterministic complete binary tree could be extended to binary search trees. This method used a classical triangular array theorem to study the convergence of sums of triangular arrays to infinitely divisible distributions. It was shown that with modifications, the same approach could be used to determine the asymptotic distribution of the number of records (or cuts) in binary search trees, i.e., in a well-characterized type of random split trees. In the second paper, renewal theory was introduced as a novel approach for studying split trees. It was shown that this theory is highly useful for investigating these types of trees. It was shown that the expected number of vertices (a random number) divided by the number of balls, n, converges to a constant as n tends to infinity. Furthermore, it was demonstrated that the number of vertices is concentrated around its mean value. New results were also presented regarding depths of balls and vertices in split trees. In the third paper, it was tested whether the methods of proof to determine the asymptotic distribution of the number of records (or cuts) used in the binary search tree, could be extended to split trees in general. Using renewal theory it was demonstrated for the overall class of random split trees that the normalized number of records (or cuts) has asymptotically a weakly 1-stable distribution. In the fourth paper, branching Markov chains were introduced to investigate split trees with immigration, i.e., CTM protocols and their generalizations. It was shown that there is a natural relationship between the Markov chain and a multi-type (Galton-Watson) process that is well adapted to study stability in the corresponding tree. A stability condition was presented to describe a phase transition deciding when the process is stable or unstable (i.e., the tree explodes). Further, the use of renewal theory also proved to be useful for studying split trees with immigration. Using this method it was demonstrated that when the tree is stable (i.e., finite), there is the same type of expression for the number of vertices as for normal split trees.
41
Moinet, Axel. "Définition d'une architecture IoT sécurisée et adaptative basée sur la blockchain." Thesis, Bourgogne Franche-Comté, 2019. http://www.theses.fr/2019UBFCK010.
Full textAbstract:
Au cours des quinze dernières années, le développement de plateformes embarquées intelligentes et les progrès des protocoles de communication radio ont permis l'émergence de réseaux de capteurs sans-fils (WSN). D'autre part, la démocratisation d'Internet et du Web, ainsi que l'augmentation des débits ont contribué à l'essor d'un nouveau paradigme : le Cloud computing. L'Internet des Objets, (IoT) ou Internet des Objets réalise la convergence entre les réseaux de capteurs et le Cloud computing. De nombreux travaux adressant les problématiques de l'IoT ont étés menés ces dix dernières années, cependant ces propositions manquent ne tiennent pas suffisamment compte des problématiques de sécurité et de protection des données. D'après Gartner, 70 % des plateformes déployées ne disposent pas d'une solution de sécurité efficace, les rendant vulnérables aux attaques. Dans le domaine des monnaies numériques, Bitcoin propose en son sein une nouvelle structure de données authentifiée et trustless permettant la décentralisation de l'enregistrement de transactions en s'appuyant sur un protocole permettant d'obtenir un consensus : la blockchain. Cette thèse se focalise sur l'utilisation de cette nouvelle structure de données dans les WSN dans un contexte IoT, comme base pour la définition d'une architecture sécurisée et adaptative basée sur la blockchain. Le but de cette architecture est d'intégrer les solutions existantes pour l'organisation du réseau et l'accès aux services de manière innovante afin de réaliser l'intégration des WSN avec l'infrastructure web; mais aussi d'y adjoindre une solution répondant aux nouveaux besoins de sécurités et contraintes spécifiques des réseaux de capteurs. Nous proposons pour cela un framework nommé Network Service Loader (NSL) en charge de la gestion de services et d'agents mobiles, auquel s'adjoint notre solution Blockchain Authentication and Trust Module (BATM) en charge de l'authentification, du contrôle d'accès, ainsi que des évaluations de confiance via l'algorithme Maximum Likelihood Trust Estimator (MLTE)During the last fifteen years, the rise of smart and wireless enabled embedded devices lead to the development of wireless sensor networks (WSN). In the same time, the emerging of Cloud computing with the development of the Internet and the Web as an everyday technology thanks to the rise of bandwidth and processing power leads to new network paradigms. The Internet of Things (IoT) primary goal is to bridge the gap between these technologies and bring WSN sensing and actuating abilities to Cloud applications. We count a significant amount of work targetting the IoT in the last decade, however they lack proper solutions to ensure data privacy and security. Gartner investigations shows that 70 % of connected and smart devices provide little or no security policies and solutions, making both user and devices vulnerable to attackers. In the field of digital currencies, Bitcoin proposed a new authenticated and trustless data structure dedicated to transactions logging in a decentralized network with the help of a consensus protocol : the blockchain. This thesis is focused on bringing the blockchain technology as a new solutions for security in decentralized WSN in the IoT, providing the basis for a secure and adaptative agent-based middleware and execution framework. This framework attempt to federate existing work regarding the architecture of the IoT, but also to tackle security issues regarding network access, agent execution and trust evaluation. To achieve this goal, we propose Network Service Loader (NSL), an agent-based middleware constructed of existing protocols in a new way, along with a new solution called Blockchain Authentication and Trust Module (BATM) dedicated to node and users authentication, access control policies, and trust evaluation through our new Maximum Likelihood Trust Estimator (MLTE) algorithm
42
Pavlo, Andrew. "Interactive, tree-based graph visualization /." Link to online version, 2006. https://ritdml.rit.edu/dspace/handle/1850/1543.
Full text
43
Penelle, Vincent. "Réécriture d’arbres de piles et traces de systèmes à compteurs." Thesis, Paris Est, 2015. http://www.theses.fr/2015PESC1122/document.
Full textAbstract:
Dans cette thèse, nous nous attachons à étudier des classes de graphes infinis et leurs propriétés, Notamment celles de vérification de modèles, d'accessibilité et de langages reconnus.Nous définissons une notion d'arbres de piles ainsi qu'une notion liée de réécriture suffixe, permettant d'étendre à la fois les automates à piles d'ordre supérieur et la réécriture suffixe d'arbres de manière minimale. Nous définissons également une notion de reconnaissabilité sur les ensembles d'opérations à l'aide d'automates qui induit une notion de reconnaissabilité sur les ensembles d'arbres de piles et une notion de normalisation des ensembles reconnaissables d'opérations analogues à celles existant sur les automates à pile d'ordre supérieur. Nous montrons que les graphes définis par ces systèmes de réécriture suffixe d'arbres de piles possèdent une FO-théorie décidable, en montrant que ces graphes peuvent être obtenu par une interprétation à ensembles finis depuis un graphe de la hiérarchie à piles.Nous nous intéressons également au problème d'algébricité des langages de traces des systèmes à compteurs et au problème lié de la stratifiabilité d'un ensemble semi-linéaire. Nous montrons que dans le cas des polyèdres d'entiers, le problème de stratifiabilité est décidable et possède une complexité coNP-complète. Ce résultat nous permet ensuite de montrer que le problème d'algébricité des traces de systèmes à compteurs plats est décidable et coNP-complet. Nous donnons également une nouvelle preuve de la décidabilité des langages de traces des systèmes d'addition de vecteurs, préalablement étudié par SchwerIn this thesis, we study classes of infinite graphs and their properties,especially the model-checking problem, the accessibility problem and therecognised languages.We define a notion of stack trees, and a related notionof ground rewriting, which is an extension of both higher-order pushdownautomata and ground tree rewriting systems. We also define a notion ofrecognisability on the sets of ground rewriting operations through operationautomata. This notion induces a notion of recognisability over sets of stacktrees and a normalisation of recognisable sets of operations, similar to theknown notions over higher-order pushdown automata. We show that the graphsdefined by these ground stack tree rewriting systems have a decidableFO-theory, by exhibiting a finite set interpretation from a graph defined bya higher-order automaton to a graph defined by a ground stack tree rewritingsystem.We also consider the context-freeness problem for counter systems, andthe related problem of stratifiability of semi-linear sets. We prove thedecidability of the stratifiability problem for integral polyhedra and that itis coNP-complete. We use this result to show that the context-freeness problemfor flat counter systems is as well coNP-complete. Finally, we give a new proofof the decidability of the context-freeness problem for vector additionsystems, previously studied by Schwer
44
Schmidt, Tina Janne [Verfasser], Peter [Akademischer Betreuer] [Gutachter] Gritzmann, Anusch [Gutachter] Taraz, and Christina G. [Gutachter] Fernandez. "On the Minimum Bisection Problem in Tree-Like and Planar Graphs : Structural and Algorithmic Results / Tina Janne Schmidt ; Gutachter: Peter Gritzmann, Anusch Taraz, Christina G. Fernandez ; Betreuer: Peter Gritzmann." München : Universitätsbibliothek der TU München, 2017. http://d-nb.info/1138359688/34.
Full text
45
Dieng, Youssou. "Décomposition arborescente des graphes planaires et routage compact." Thesis, Bordeaux 1, 2009. http://www.theses.fr/2009BOR13855/document.
Full textAbstract:
Savoir comment transmettre une information est fondamental dans un réseau. Il est essentiel que chaque entité du réseau soit capable de décider localement, avec sa vue du réseau, du chemin par lequel l'information doit passer. Ainsi, il est souvent utile d'étudier la topologie du réseau, modélisée par un graphe, pour répondre à ces exigences. Nous nous intéressons dans un premier temps, à la décomposition arborescente des graphes planaires. En effet, comme dans beaucoup de problèmes de graphes, l'étude de la topologie des graphes nous conduit à procéder à une décomposition du graphe afin d'exploiter les propriétés structurelles qui en découlent. En suite, nous nous sommes aussi intéressés à la structure des graphes qui excluent un mineur H, en particulier le graphe K_{2,r}. Ces travaux nous ont permis d'améliorer les bornes actuelles connues sur la largeur arborescente de ces graphes. Dans la dernière partie, nous abordons le problème du routage compact. Nous nous sommes intéressés aux schémas de routage de plus courts chemins utilisant des adresses, des tables de routage de tailles optimales de O(log n) bits, où n est le nombre de sommets du graphe. Nous proposons un tel schéma de routage pour une famille de graphes valués contenant les arbres et les graphes planaire-extérieursIn a network, it is crucial to know how to construct an efficent routing scheme. It is fundamental for each entity with its local knowledge of the network, to be able to decide on which link to forward messages. Thus, it is important to sutdy the underlying network topology in order to design routing schemes. In the first part of this thesis, we construct a new tree-decomposition for planar graphs. In fact, as in many graph problems, the study of the graph structure leads to do a tree-decomposition for exploiting structural propertys of the graphs. In second part, we studied the structure of H-minor free graphs, in particular whenever H = K_{2,r}. Our results improve upon previous known bounds about the tree-width of K_{2,r}-minor free graphs. At last, we treat the problème of compact routing scheme. More precisely, we are interested in shortest-path routing schemes that use O(\log n) bits for addresses, headers and routing tables, where n is the number of vertices in the graph. We propose such a routing scheme for a large family of weighted graphs including outerplanar graphs
46
Okoth, Isaac Owino. "Combinatorics of oriented trees and tree-like structures." Thesis, Stellenbosch : Stellenbosch University, 2015. http://hdl.handle.net/10019.1/96860.
Full textAbstract:
Thesis (PhD)--Stellenbosch University, 2015.ENGLISH ABSTRACT : In this thesis, a number of combinatorial objects are enumerated. Du and Yin as well as Shin and Zeng (by a different approach) proved an elegant formula for the number of labelled trees with respect to a given in degree sequence, where each edge is oriented from a vertex of lower label towards a vertex of higher label. We refine their result to also take the number of sources (vertices of in degree 0) or sinks (vertices of out degree 0) into account. We find formulas for the mean and variance of the number of sinks or sources in these trees. We also obtain a differential equation and a functional equation satisfied by the generating function for these trees. Analogous results for labelled trees with two marked vertices, related to functional digraphs, are also established. We extend the work to count reachable vertices, sinks and leaf sinks in these trees. Among other results, we obtain a counting formula for the number of labelled trees on n vertices in which exactly k vertices are reachable from a given vertex v and also the average number of vertices that are reachable from a specified vertex in labelled trees of order n. In this dissertation, we also enumerate certain families of set partitions and related tree-like structures. We provide a proof for a formula that counts connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain coherence condition and then establish a bijection between these families and the set of labelled free k-ary cacti with a given vertex-degree distribution. We then show that the formula also counts coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We extend the work to count coloured oriented cacti and coloured cacti. Noncrossing trees and related tree-like structures are also considered in this thesis. Specifically, we establish formulas for locally oriented noncrossing trees with a given number of sources and sinks, and also with given indegree and outdegree sequences. The work is extended to obtain the average number of reachable vertices in these trees. We then generalise the concept of noncrossing trees to find formulas for the number of noncrossing Husimi graphs, cacti and oriented cacti. The study is further extended to find formulas for the number of bicoloured noncrossing Husimi graphs and the number of noncrossing connected cycle-free pairs of set partitions.
AFRIKAANSE OPSOMMING : In hierdie tesis word ’n aantal kombinatoriese objekte geenumereer. Du en Yin asook Shin en Zeng (deur middel van ’n ander benadering) het ’n elegante formule vir die aantal geëtiketteerde bome met betrekking tot ’n gegewe ingangsgraadry, waar elke lyn van die nodus met die kleiner etiket na die nodus met die groter etiket toe georiënteer word. Ons verfyn hul resultaat deur ook die aantal bronne (nodusse met ingangsgraad 0) en putte (nodusse met uitgangsgraad 0) in ag te neem. Ons vind formules vir die gemiddelde en variansie van die aantal putte of bronne in hierdie bome. Ons bepaal verder ’n differensiaalvergelyking en ’n funksionaalvergelyking wat deur die voortbringende funksie van hierdie bome bevredig word. Analoë resultate vir geëtiketteerde bome met twee gemerkte nodusse (wat verwant is aan funksionele digrafieke), is ook gevind. Ons gaan verder voort deur ook bereikbare nodusse, bronne en putte in hierdie bome at te tel. Onder andere verkry ons ’n formule vir die aantal geëtiketteerde bome met n nodusse waarin presies k nodusse vanaf ’n gegewe nodus v bereikbaar is asook die gemiddelde aantal nodusse wat bereikbaar is vanaf ’n gegewe nodus. Ons enumereer in hierdie tesis verder sekere families van versamelingsverdelings en soortgelyke boom-vormige strukture. Ons gee ’n bewys vir ’n formule wat die aantal van samehangende siklus-vrye families van k versamelingsverdelings op {1, . . . , n} wat ’n sekere koherensie-vereiste bevredig, en ons beskryf ’n bijeksie tussen hierdie familie en die versameling van geëtiketteerde vrye k-êre kaktusse met ’n gegewe nodus-graad-verdeling. Ons toon ook dat hierdie formule ook gekleurde Husimi-grafieke tel waar blokke van dieselfde kleur nie insident met mekaar mag wees nie. Ons tel verder ook gekleurde georiënteerde kaktusse en gekleurde kaktusse. Nie-kruisende bome en soortgelyke boom-vormige strukture word in hierdie tesis ook beskou. On bepaal spesifiek formules vir lokaal georiënteerde nie-kruisende bome wat ’n gegewe aantal bronne en putte het asook nie-kruisende bome met gegewe ingangs- en uitgangsgraadrye. Ons gaan voort deur die gemiddelde aantal bereikbare nodusse in hierdie bome te bepaal. Ons veralgemeen dan die konsep van nie-kruisende bome en vind formules vir die aantal nie-kruisende Husimi-grafieke, kaktusse en georiënteerde kaktusse. Laastens vind ons ’n formule vir die aantaal tweegekleurde nie-kruisende Husimi-grafieke en die aantal nie-kruisende samehangende siklus-vrye pare van versamelingsverdelings.
47
Irniger, Christophe-André. "Graph matching filtering databases of graphs using machine learning techniques." Berlin Aka, 2005. http://deposit.ddb.de/cgi-bin/dokserv?id=2677754&prov=M&dok_var=1&dok_ext=htm.
Full text
48
Curado, Manuel. "Structural Similarity: Applications to Object Recognition and Clustering." Doctoral thesis, Universidad de Alicante, 2018. http://hdl.handle.net/10045/98110.
Full textAbstract:
In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of $m$-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape simplification (sparsification) and early prediction of AD.Ministerio de Economía, Industria y Competitividad (Referencia TIN2012-32839 BES-2013-064482)
49
Koessler, Denise Renee. "A Predictive Model for Secondary RNA Structure Using Graph Theory and a Neural Network." Digital Commons @ East Tennessee State University, 2010. https://dc.etsu.edu/etd/1684.
Full textAbstract:
In this work we use a graph-theoretic representation of secondary RNA structure found in the database RAG: RNA-As-Graphs. We model the bonding of two RNA secondary structures to form a larger structure with a graph operation called merge. The resulting data from each tree merge operation is summarized and represented by a vector. We use these vectors as input values for a neural network and train the network to recognize a tree as RNA-like or not based on the merge data vector.
The network correctly assigned a high probability of RNA-likeness to trees identified as RNA-like in the RAG database, and a low probability of RNA-likeness to those classified as not RNA-like in the RAG database. We then used the neural network to predict the RNA-likeness of all the trees of order 9. The use of a graph operation to theoretically describe the bonding of secondary RNA is novel.
50
Schwartz, Andrew Michael. "Decompositions of graphs and trees /." Available to subscribers only, 2008. http://proquest.umi.com/pqdweb?did=1594477631&sid=6&Fmt=2&clientId=1509&RQT=309&VName=PQD.
Full text