You searched for subject:(Even hole free graphs).
Showing records 1 – 30 of
11926 total matches.
◁ [1] [2] [3] [4] [5] … [398] ▶
1.
Aline Alves da Silva.
DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos.
Degree: Master, 2007, Universidade Federal do Ceará
URL: http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 
;
► Os conceitos de DecomposiÃÃo em Ãrvore e Largura em Ãrvore foram introduzidos por Robertson e Seymour em sua sÃrie de artigos sobre menores de grafos,…
(more)
▼ Os conceitos de DecomposiÃÃo em Ãrvore e Largura em Ãrvore foram introduzidos por Robertson e Seymour em sua sÃrie de artigos sobre menores de grafos, publicados ao longo da dÃcada de 90. Sabe-se que muitos problemas NP - difÃceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposiÃÃo em Ãrvore de G de largura limitada. Logo, limitar a largura em Ãrvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras mÃtricas limitadas em valores baixos (por exemplo, nÃmero cromÃtico), nÃo possui largura em Ãrvore limitada. Desta forma, uma alternativa à restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nÃs investigamos a classe dos grafos planares livres de buracos pares. NÃs mostramos que se G à um grafo planar livre de buracos pares, entÃo ele nÃo contÃm uma subdivisÃo de uma grade 10  10. Portanto, se os menores grades de G sÃo obtidos de subdivisÃes G tem largura em Ãrvore no mÃximo 49. AlÃm disso, dois algoritmos nÃo exatos polinomiais para computar uma decomposiÃÃo em Ãrvore de um grafo planar livre de buracos pares sÃo apresentados, ambos baseados em caracterizaÃÃes conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposiÃÃo em Ãrvore à construÃda a partir
de grafos bÃsicos pela concatenaÃÃo de decomposiÃÃes em Ãrvores de pedaÃos pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposiÃÃo em Ãrvore à construÃda pela inclusÃo dos vÃrtices de G um a um, seguindo sua ordem bi-simplicial.
The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10Â10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the Ârst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order.
Advisors/Committee Members: Ricardo Cordeiro CorrÃa, Sulamita Klein, ClÃudia Linhares Sales.
Subjects/Keywords: CIENCIA DA COMPUTACAO; Grafos planares, grafos livres de buracos pares,
largura em Ãrvore, teoria de Grafos.; Planar Graphs, even-hole-free graphs, treewidth, graph
theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Silva, A. A. d. (2007). DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos. (Masters Thesis). Universidade Federal do Ceará. Retrieved from http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;
Chicago Manual of Style (16th Edition):
Silva, Aline Alves da. “DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos.” 2007. Masters Thesis, Universidade Federal do Ceará. Accessed January 19, 2021.
http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;.
MLA Handbook (7th Edition):
Silva, Aline Alves da. “DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos.” 2007. Web. 19 Jan 2021.
Vancouver:
Silva AAd. DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos. [Internet] [Masters thesis]. Universidade Federal do Ceará 2007. [cited 2021 Jan 19].
Available from: http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;.
Council of Science Editors:
Silva AAd. DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos. [Masters Thesis]. Universidade Federal do Ceará 2007. Available from: http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;
2.
Le, Ngoc Khang.
Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.
Degree: Docteur es, Informatique, 2018, Lyon
URL: http://www.theses.fr/2018LYSEN021
► Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans…
(more)
▼ Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interdits.
Graphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the…
Advisors/Committee Members: Trotignon, Nicolas (thesis director).
Subjects/Keywords: Coloration de graphe; Reconnaissance de graphe; Sous-graphes induits; Graphes sans ISK4; Graphes sans trou pair; Coloration gloutonne connexe; Graph coloring; Graph recognition; Induced subgraphs; ISK4-free graphs; Even-hole-free graphs; Connected greedy coloring
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Le, N. K. (2018). Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. (Doctoral Dissertation). Lyon. Retrieved from http://www.theses.fr/2018LYSEN021
Chicago Manual of Style (16th Edition):
Le, Ngoc Khang. “Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.” 2018. Doctoral Dissertation, Lyon. Accessed January 19, 2021.
http://www.theses.fr/2018LYSEN021.
MLA Handbook (7th Edition):
Le, Ngoc Khang. “Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes.” 2018. Web. 19 Jan 2021.
Vancouver:
Le NK. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. [Internet] [Doctoral dissertation]. Lyon; 2018. [cited 2021 Jan 19].
Available from: http://www.theses.fr/2018LYSEN021.
Council of Science Editors:
Le NK. Detecting and Coloring some Graph Classes : Détection et coloration de certaines classes de graphes. [Doctoral Dissertation]. Lyon; 2018. Available from: http://www.theses.fr/2018LYSEN021
University of Minnesota
3.
Stewart, Danielle.
Even Harmonious Labelings of Disconnected Graphs.
Degree: MS, Applied and Computational Mathematics, 2015, University of Minnesota
URL: http://hdl.handle.net/11299/174719
► A graph G with q edges is called it{graceful} if there is an injection from the vertices of G to the set {0,1,…,q} such that…
(more)
▼ A graph G with q edges is called it{graceful} if there is an injection from the vertices of G to the set {0,1,…,q} such that when each edge xy is assigned the label |f(x)-f(y)|, the resulting edge labels are distinct. This notion as well as a number of other functions from a graph to a set of non-negative integers were studied as tools for decomposing the complete graph into isomorphic subgraphs. A graph G with q edges is said to be harmonious if there is an injection f from the vertices of G to the group of integers modulo q such that when each edge xy is assigned the label f(x)+f(y) (mod q), the resulting edge labels are distinct. If G is a tree, exactly one label may be used on two vertices. Over the years, many variations of these two concepts have been studied and hundreds of articles have been written on these topics. We study a variant of harmonious labeling. A function f is said to be an even harmonious labeling of a graph G with q edges if f is an injection from the vertices of G to the integers from 0 to 2q and the induced function f^* from the edges of G to {0,2,…,2(q-1)} defined by f^*(xy)=f(x)+f(y) (mod 2q) is bijective. Only a few papers have been written on even harmonious labeling. This paper focuses on finding even harmonious labelings for disjoint graphs. Among the families we investigate are: the disjoint union of cycles and stars, unions of cycles with paths, and unions of squares of paths.
Subjects/Keywords: Disconnected Graphs; Even Harmonious; Graph Labeling; Graph Theory; Harmonious; Properly Even Harmonious
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Stewart, D. (2015). Even Harmonious Labelings of Disconnected Graphs. (Masters Thesis). University of Minnesota. Retrieved from http://hdl.handle.net/11299/174719
Chicago Manual of Style (16th Edition):
Stewart, Danielle. “Even Harmonious Labelings of Disconnected Graphs.” 2015. Masters Thesis, University of Minnesota. Accessed January 19, 2021.
http://hdl.handle.net/11299/174719.
MLA Handbook (7th Edition):
Stewart, Danielle. “Even Harmonious Labelings of Disconnected Graphs.” 2015. Web. 19 Jan 2021.
Vancouver:
Stewart D. Even Harmonious Labelings of Disconnected Graphs. [Internet] [Masters thesis]. University of Minnesota; 2015. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/11299/174719.
Council of Science Editors:
Stewart D. Even Harmonious Labelings of Disconnected Graphs. [Masters Thesis]. University of Minnesota; 2015. Available from: http://hdl.handle.net/11299/174719
Wilfrid Laurier University
4.
Gorbonos, Elizabeth.
Separability and Vertex Ordering of Graphs.
Degree: 2019, Wilfrid Laurier University
URL: https://scholars.wlu.ca/etd/2148
► Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique…
(more)
▼ Many graph optimization problems, such as finding an optimal coloring, or a largest clique, can be solved by a divide-and-conquer approach. One such well-known technique is decomposition by clique separators where a graph is decomposed into special induced subgraphs along their clique separators. While the most common practice of this method employs minimal clique separators, in this work we study other variations as well. We strive to characterize their structure and in particular the bound on the number of atoms. In fact, we strengthen the known bounds for the general clique cutset decomposition and the minimal clique separator decomposition. Graph ordering is the arrangement of a graph’s vertices according to a certain logic and is a useful tool in optimization problems. Special types of vertices are often recognized in graph classes, for instance it is well-known every chordal graph contains a simplicial vertex. Vertex-ordering, based on such properties, have originated many linear time algorithms. We propose to define a new family named SE-Class such that every graph belonging to this family inherently contains a simplicial extreme, that is a vertex which is either simplicial or has exactly two neighbors which are non-adjacent. Our family lends itself to an ordering based on simplicial extreme vertices (named SEO) which we demonstrate to be advantageous for the coloring and maximum clique problems. In addition, we examine the relation of SE-Class to the family of (Even-Hole, Kite)-free graphs and show a linear time generation of SEO for (Even-Hole, Diamond, Claw)-free graphs. We showcase the applications of those two core tools, namely clique-based decomposition and vertex ordering, on the (Even-Hole, Kite)-free family.
Subjects/Keywords: graph theory; decomposition; clique cutset; simplicial extreme; even-hole; kite; Theory and Algorithms
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Gorbonos, E. (2019). Separability and Vertex Ordering of Graphs. (Thesis). Wilfrid Laurier University. Retrieved from https://scholars.wlu.ca/etd/2148
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Thesis, Wilfrid Laurier University. Accessed January 19, 2021.
https://scholars.wlu.ca/etd/2148.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Gorbonos, Elizabeth. “Separability and Vertex Ordering of Graphs.” 2019. Web. 19 Jan 2021.
Vancouver:
Gorbonos E. Separability and Vertex Ordering of Graphs. [Internet] [Thesis]. Wilfrid Laurier University; 2019. [cited 2021 Jan 19].
Available from: https://scholars.wlu.ca/etd/2148.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Gorbonos E. Separability and Vertex Ordering of Graphs. [Thesis]. Wilfrid Laurier University; 2019. Available from: https://scholars.wlu.ca/etd/2148
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Vanderbilt University
5.
Marshall, Emily Abernethy.
Hamiltonicity and Structure of Classes of Minor-Free Graphs.
Degree: PhD, Mathematics, 2014, Vanderbilt University
URL: http://hdl.handle.net/1803/10999
► The main results of this dissertation are Hamiltonicity and structural results for graphs on surfaces and graphs with certain forbidden minors. The first result is…
(more)
▼ The main results of this dissertation are Hamiltonicity and structural results for
graphs on surfaces and
graphs with certain forbidden minors.
The first result is related to a conjecture due to Grunbaum and Nash-Williams which states that all 4-connected
graphs on the torus are Hamiltonian. One approach to prove this conjecture is to extend the proof techniques of a result due to Thomas and Yu which says that every edge of a 4-connected projective-planar graph is on a Hamilton cycle. However the analogous result is not true for
graphs on the torus. Thomassen
provided examples of 4-connected toroidal
graphs such that some edges of each graph are not contained in any Hamilton cycle. Our result shows that these examples are critical in a certain sense.
The second and third results concern minor-
free graphs. Tutte proved that every 4-connected planar
graph is Hamiltonian. Not all 3-connected planar
graphs are Hamiltonian, however: the Herschel graph is one example. Our second result proves that all 3-connected, planar, K
2,5-minor-
free graphs are Hamiltonian. We give examples to show that the K
2,5-minor-
free condition cannot be weakened to K
2,6-minor-
free. The final result is a complete characterization of all K
2,4-minor-
free graphs. To prove both of these results we first provide a characterization of rooted-K
2,2-minor-
free graphs. We also prove several useful results concerning Hamilton paths in rooted K
2,2-minor-
free graphs.
Advisors/Committee Members: Xiaoya Zha (committee member), Denis Osin (committee member), Michael Mihalik (committee member), Jeremy Spinrad (committee member), Mark Ellingham (Committee Chair).
Subjects/Keywords: minor-free graphs; hamilton cycles; graph theory
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Marshall, E. A. (2014). Hamiltonicity and Structure of Classes of Minor-Free Graphs. (Doctoral Dissertation). Vanderbilt University. Retrieved from http://hdl.handle.net/1803/10999
Chicago Manual of Style (16th Edition):
Marshall, Emily Abernethy. “Hamiltonicity and Structure of Classes of Minor-Free Graphs.” 2014. Doctoral Dissertation, Vanderbilt University. Accessed January 19, 2021.
http://hdl.handle.net/1803/10999.
MLA Handbook (7th Edition):
Marshall, Emily Abernethy. “Hamiltonicity and Structure of Classes of Minor-Free Graphs.” 2014. Web. 19 Jan 2021.
Vancouver:
Marshall EA. Hamiltonicity and Structure of Classes of Minor-Free Graphs. [Internet] [Doctoral dissertation]. Vanderbilt University; 2014. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/1803/10999.
Council of Science Editors:
Marshall EA. Hamiltonicity and Structure of Classes of Minor-Free Graphs. [Doctoral Dissertation]. Vanderbilt University; 2014. Available from: http://hdl.handle.net/1803/10999
University of Windsor
6.
Khanduja, Sudiksha.
Weakly Chordal Graphs: An Experimental Study.
Degree: MS, Computer Science, 2020, University of Windsor
URL: https://scholar.uwindsor.ca/etd/8377
► Graph theory is an important field that enables one to get general ideas about graphs and their properties. There are many situations (such as generating…
(more)
▼ Graph theory is an important field that enables one to get general ideas about
graphs and their properties. There are many situations (such as generating all linear layouts of weakly chordal
graphs) where we want to generate instances to test algorithms for weakly chordal
graphs. In my thesis, we address the algorithmic problem of generating weakly chordal
graphs. A graph G=(V, E), where V is its vertices and E is its edges, is called a weakly chordal graph, if neither G nor its complement G', contains an induced chordless cycle on five or more vertices.
Our work is in two parts. In the first part, we carry out a comparative study of two existing algorithms for generating weakly chordal
graphs. The first algorithm for generating weakly chordal
graphs repeatedly finds a two-pair and adds an edge between them. The second-generation algorithm starts by constructing a tree and then generates an orthogonal layout (also weakly chordal graph) based on this tree. Edges are then inserted into this orthogonal layout until there are m edges. The output
graphs from these two methods are compared with respect to several parameters like the number of four cycles, run times, chromatic number, the number of non-two-pairs in the
graphs generated by the second method.
In the second part, we propose an algorithm for generating weakly chordal
graphs by edge deletions starting from an arbitrary input random graph. The algorithm starts with an arbitrary graph to be able to generate a weakly chordal graph by the basis of edge deletion. The algorithm iterates by maintaining weak chordality by preventing any
hole or antihole configurations being formed for any successful deletion of an edge.
Advisors/Committee Members: Asish Mukhopadhyay.
Subjects/Keywords: Antihole; Generation Algorithm; Graph Theory; Hole; Weakly Chordal Graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Khanduja, S. (2020). Weakly Chordal Graphs: An Experimental Study. (Masters Thesis). University of Windsor. Retrieved from https://scholar.uwindsor.ca/etd/8377
Chicago Manual of Style (16th Edition):
Khanduja, Sudiksha. “Weakly Chordal Graphs: An Experimental Study.” 2020. Masters Thesis, University of Windsor. Accessed January 19, 2021.
https://scholar.uwindsor.ca/etd/8377.
MLA Handbook (7th Edition):
Khanduja, Sudiksha. “Weakly Chordal Graphs: An Experimental Study.” 2020. Web. 19 Jan 2021.
Vancouver:
Khanduja S. Weakly Chordal Graphs: An Experimental Study. [Internet] [Masters thesis]. University of Windsor; 2020. [cited 2021 Jan 19].
Available from: https://scholar.uwindsor.ca/etd/8377.
Council of Science Editors:
Khanduja S. Weakly Chordal Graphs: An Experimental Study. [Masters Thesis]. University of Windsor; 2020. Available from: https://scholar.uwindsor.ca/etd/8377
University of Maryland
7.
Sharon, Gilad.
MODELING THE PHYSICS OF FAILURE FOR ELECTRONIC PACKAGING COMPONENTS SUBJECTED TO THERMAL AND MECHANICAL LOADING.
Degree: Mechanical Engineering, 2011, University of Maryland
URL: http://hdl.handle.net/1903/11937
► This dissertation presents three separate studies that examined electronic components using numerical modeling approaches. The use of modeling techniques provided a deeper understanding of the…
(more)
▼ This dissertation presents three separate studies that examined electronic components using numerical modeling approaches. The use of modeling techniques provided a deeper understanding of the physical phenomena that contribute to the formation of cracks inside ceramic capacitors, damage inside plated through holes, and to dynamic fracture of MEMS structures. The modeling yielded numerical substantiations for previously proposed theoretical explanations.
Multi-Layer Ceramic Capacitors (MLCCs) mounted with stiffer lead-
free solder have shown greater tolerance than tin-lead solder for single cycle board bending loads with low strain rates. In contrast, flexible terminations have greater tolerance than stiffer standard terminations under the same conditions. It has been proposed that residual stresses in the capacitor account for this disparity. These stresses have been attributed to the higher solidification temperature of lead
free solders coupled with the CTE mismatch between the board and the capacitor ceramic. This research indicated that the higher solidification temperatures affected the residual stresses.
Inaccuracies in predicting barrel failures of plated through holes are suspected to arise from neglecting the effects of the reflow process on the copper material. This research used thermo mechanical analysis (TMA) results to model the damage in the copper above the glass transition temperature (Tg) during reflow. Damage estimates from the hysteresis plots were used to improve failure predictions.
Modeling was performed to examine the theory that brittle fracture in MEMS structures is not affected by strain rates. Numerical modeling was conducted to predict the probability of dynamic failure caused by shock loads. The models used a quasi-static global gravitational load to predict the probability of brittle fracture.
The research presented in this dissertation explored drivers for failure mechanisms in flex cracking of capacitors, barrel failures in plated through holes, and dynamic fracture of MEMS. The studies used numerical modeling to provide new insights into underlying physical phenomena. In each case, theoretical explanations were examined where difficult geometries and complex material properties made it difficult or impossible to obtain direct measurements.
Advisors/Committee Members: Barker, Donald D (advisor).
Subjects/Keywords: Engineering; Capacitor cracking; Lead free; MEMS; Modeling; Plated Through Hole; Solder
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Sharon, G. (2011). MODELING THE PHYSICS OF FAILURE FOR ELECTRONIC PACKAGING COMPONENTS SUBJECTED TO THERMAL AND MECHANICAL LOADING. (Thesis). University of Maryland. Retrieved from http://hdl.handle.net/1903/11937
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Sharon, Gilad. “MODELING THE PHYSICS OF FAILURE FOR ELECTRONIC PACKAGING COMPONENTS SUBJECTED TO THERMAL AND MECHANICAL LOADING.” 2011. Thesis, University of Maryland. Accessed January 19, 2021.
http://hdl.handle.net/1903/11937.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Sharon, Gilad. “MODELING THE PHYSICS OF FAILURE FOR ELECTRONIC PACKAGING COMPONENTS SUBJECTED TO THERMAL AND MECHANICAL LOADING.” 2011. Web. 19 Jan 2021.
Vancouver:
Sharon G. MODELING THE PHYSICS OF FAILURE FOR ELECTRONIC PACKAGING COMPONENTS SUBJECTED TO THERMAL AND MECHANICAL LOADING. [Internet] [Thesis]. University of Maryland; 2011. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/1903/11937.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Sharon G. MODELING THE PHYSICS OF FAILURE FOR ELECTRONIC PACKAGING COMPONENTS SUBJECTED TO THERMAL AND MECHANICAL LOADING. [Thesis]. University of Maryland; 2011. Available from: http://hdl.handle.net/1903/11937
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Texas A&M University
8.
Pearce, Roger Allan.
Scalable Parallel Algorithms for Massive Scale-free Graphs.
Degree: PhD, Computer Science, 2013, Texas A&M University
URL: http://hdl.handle.net/1969.1/151937
► Efficiently storing and processing massive graph data sets is a challenging problem as researchers seek to leverage “Big Data” to answer next-generation scientific questions. New…
(more)
▼ Efficiently storing and processing massive graph data sets is a challenging problem as researchers seek to leverage “Big Data” to answer next-generation scientific questions. New techniques are required to process large scale-
free graphs in shared, distributed, and external memory. This dissertation develops new techniques to parallelize the storage, computation, and communication for scale-
free graphs with high-degree vertices. Our work facilitates the processing of large real-world graph datasets through the development of parallel algorithms and tools that scale to large computational and memory resources, overcoming challenges not addressed by existing techniques. Our aim is to scale to trillions of edges, and our research is targeted at leadership class supercomputers, clusters with local non-volatile memory, and shared memory systems.
We present three novel techniques to address scaling challenges in processing large scale-
free graphs. We apply an asynchronous graph traversal technique using prioritized visitor queues that is capable of tolerating data latencies to the external graph storage media and message passing communication. To accommodate large high-degree vertices, we present an edge list partitioning technique that evenly partitions
graphs containing high-degree vertices. Finally, we propose a technique we call distributed delegates that distributes and parallelizes the storage, computation, and communication when processing high-degree vertices. The edges of high-degree vertices are distributed, providing additional opportunities for parallelism not present in existing methods.
We apply our techniques to multiple graph algorithms: Breadth-First Search, Single Source Shortest Path, Connected Components, K-Core decomposition, Triangle Counting, and Page Rank. Our experimental study of these algorithms demonstrates excellent scalability on supercomputers, clusters with non-volatile memory, and shared memory systems. Our study includes multiple synthetic scale-
free graph models, the largest of which has trillion edges, and real-world input
graphs. On a supercomputer, we demonstrate scalability up to 131K processors, and improve the best known Graph500 results for IBM BG/P Intrepid by 15%.
Advisors/Committee Members: Amato, Nancy M (advisor), Choe, Yoonsuck (committee member), Rauchwerger, Lawrence (committee member), Adams, Marvin L (committee member), Gokhale, Maya (committee member).
Subjects/Keywords: parallel algorithms; graph algorithms; scale-free graphs; graph partitioning
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Pearce, R. A. (2013). Scalable Parallel Algorithms for Massive Scale-free Graphs. (Doctoral Dissertation). Texas A&M University. Retrieved from http://hdl.handle.net/1969.1/151937
Chicago Manual of Style (16th Edition):
Pearce, Roger Allan. “Scalable Parallel Algorithms for Massive Scale-free Graphs.” 2013. Doctoral Dissertation, Texas A&M University. Accessed January 19, 2021.
http://hdl.handle.net/1969.1/151937.
MLA Handbook (7th Edition):
Pearce, Roger Allan. “Scalable Parallel Algorithms for Massive Scale-free Graphs.” 2013. Web. 19 Jan 2021.
Vancouver:
Pearce RA. Scalable Parallel Algorithms for Massive Scale-free Graphs. [Internet] [Doctoral dissertation]. Texas A&M University; 2013. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/1969.1/151937.
Council of Science Editors:
Pearce RA. Scalable Parallel Algorithms for Massive Scale-free Graphs. [Doctoral Dissertation]. Texas A&M University; 2013. Available from: http://hdl.handle.net/1969.1/151937
Indian Institute of Science
9.
Goyal, Prachi.
Parameterized Complexity of Maximum Edge Coloring in Graphs.
Degree: MSc Engg, Faculty of Engineering, 2018, Indian Institute of Science
URL: http://etd.iisc.ac.in/handle/2005/3255
► The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent…
(more)
▼ The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints.
We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. The question is very well motivated by the problem of channel assignment in wireless networks. This problem is NP-hard for q ≥ 2, and has been well-studied from the point of view of approximation.
This problem has not been studied in the parameterized context before. Hence as a next step, this thesis investigates the parameterized complexity of this problem where the standard parameter is the solution size. The main focus of the work is the special case of q=2 ,i.e. MAXIMUM EDGE 2-COLORING which is theoretically intricate and practically relevant in the wireless networks setting.
We first show an exponential kernel for the MAXIMUM EDGE q-COLORING problem where q is a fixed constant and q ≥ 2.We do a more specific analysis for the kernel of the MAXIMUM EDGE 2-COLORING problem. The kernel obtained here is still exponential in size but is better than the kernel obtained for MAXIMUM EDGE q-COLORING problem in case of q=2.
We then show a fixed parameter tractable algorithm for the MAXIMUM EDGE 2-COLORING problem with a running time of O*∗(kO(k)).We also show a fixed parameter tractable algorithm for the MAXIMUM EDGE q-COLORING problem with a running time of O∗(kO(qk) qO(k)).
The fixed parameter tractability of the dual parametrization of the MAXIMUM EDGE 2-COLORING problem is established by arguing a linear vertex kernel for the problem. We also show that the MAXIMUM EDGE 2-COLORING problem remains hard on
graphs where the maximum degree is a constant and also on
graphs without cycles of length four. In both these cases, we obtain quadratic kernels.
A closely related variant of the problem is the question of MAX EDGE{1,2-}COLORING. For this problem, the vertices in the input graph may have different qε,{1.2} values and the goal is to use at least k colors for the edge coloring of the graph such that every vertex sees at most q colors, where q is either one or two. We show that the MAX EDGE{1,2}-COLORING problem is W[1]-hard on
graphs that have no cycles of length four.
Advisors/Committee Members: Chandran, Sunil (advisor).
Subjects/Keywords: Graph Theory; Graphs; Graphs - Coloring; Parameterized Complexity; Maximum Edge Coloring (Graphs); Fixed Parameter Tractable Algorithms; Kernelization; Graph Edge Coloring; FPT Algorithm; Polynomial Kernel; C4-free Graphs; Computer Science
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Goyal, P. (2018). Parameterized Complexity of Maximum Edge Coloring in Graphs. (Masters Thesis). Indian Institute of Science. Retrieved from http://etd.iisc.ac.in/handle/2005/3255
Chicago Manual of Style (16th Edition):
Goyal, Prachi. “Parameterized Complexity of Maximum Edge Coloring in Graphs.” 2018. Masters Thesis, Indian Institute of Science. Accessed January 19, 2021.
http://etd.iisc.ac.in/handle/2005/3255.
MLA Handbook (7th Edition):
Goyal, Prachi. “Parameterized Complexity of Maximum Edge Coloring in Graphs.” 2018. Web. 19 Jan 2021.
Vancouver:
Goyal P. Parameterized Complexity of Maximum Edge Coloring in Graphs. [Internet] [Masters thesis]. Indian Institute of Science; 2018. [cited 2021 Jan 19].
Available from: http://etd.iisc.ac.in/handle/2005/3255.
Council of Science Editors:
Goyal P. Parameterized Complexity of Maximum Edge Coloring in Graphs. [Masters Thesis]. Indian Institute of Science; 2018. Available from: http://etd.iisc.ac.in/handle/2005/3255
Queen Mary, University of London
10.
Ball, Neville.
Random Structures.
Degree: PhD, 2015, Queen Mary, University of London
URL: http://qmro.qmul.ac.uk/xmlui/handle/123456789/7902
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.658663
► For many combinatorial objects we can associate a natural probability distribution on the members of the class, and we can then call the resulting class…
(more)
▼ For many combinatorial objects we can associate a natural probability distribution on the members of the class, and we can then call the resulting class a class of random structures. Random structures form good models of many real world problems, in particular real networks and disordered media. For many such problems, the systems under consideration can be very large, and we often care about whether a property holds most of the time. In particular, for a given class of random structures, we say that a property holds with high probability if the probability that that property holds tends to one as the size of the structures increase. We examine several classes of random structures with real world applications, and look at some properties of each that hold with high probability. First we look at percolation in 3 dimensional lattices, giving a method for producing rigorous confidence intervals on the percolation threshold. Next we look at random geometric graphs, first examining the connectivity thresholds of nearest neighbour models, giving good bounds on the threshold for a new variation on these models useful for modelling wireless networks, and then look at the cop number of the Gilbert model. Finally we look at the structure of random sum-free sets, in particular examining what the possible densities of such sets are, what substructures they can contain, and what superstructures they belong to.
Subjects/Keywords: 519.2; random structures; Probabilistic tools; geometric graphs; Sum-Free Sets; combinatorial objects
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Ball, N. (2015). Random Structures. (Doctoral Dissertation). Queen Mary, University of London. Retrieved from http://qmro.qmul.ac.uk/xmlui/handle/123456789/7902 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.658663
Chicago Manual of Style (16th Edition):
Ball, Neville. “Random Structures.” 2015. Doctoral Dissertation, Queen Mary, University of London. Accessed January 19, 2021.
http://qmro.qmul.ac.uk/xmlui/handle/123456789/7902 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.658663.
MLA Handbook (7th Edition):
Ball, Neville. “Random Structures.” 2015. Web. 19 Jan 2021.
Vancouver:
Ball N. Random Structures. [Internet] [Doctoral dissertation]. Queen Mary, University of London; 2015. [cited 2021 Jan 19].
Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/7902 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.658663.
Council of Science Editors:
Ball N. Random Structures. [Doctoral Dissertation]. Queen Mary, University of London; 2015. Available from: http://qmro.qmul.ac.uk/xmlui/handle/123456789/7902 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.658663
11.
森本, 真一.
時系列データに基づいた Scale Free Graph モデルに関する研究.
Degree: Japan Advanced Institute of Science and Technology / 北陸先端科学技術大学院大学
URL: http://hdl.handle.net/10119/8101
Supervisor: 上原隆平
情報科学研究科
修士
Subjects/Keywords: Blog データ, Scale Free Graph, Interval Graph, Max-Tolerance Graph; Blog data, scale free graphs, interval graphs, max-tolerance graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
森本, . (n.d.). 時系列データに基づいた Scale Free Graph モデルに関する研究. (Thesis). Japan Advanced Institute of Science and Technology / 北陸先端科学技術大学院大学. Retrieved from http://hdl.handle.net/10119/8101
Note: this citation may be lacking information needed for this citation format:
No year of publication.
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
森本, 真一. “時系列データに基づいた Scale Free Graph モデルに関する研究.” Thesis, Japan Advanced Institute of Science and Technology / 北陸先端科学技術大学院大学. Accessed January 19, 2021.
http://hdl.handle.net/10119/8101.
Note: this citation may be lacking information needed for this citation format:
No year of publication.
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
森本, 真一. “時系列データに基づいた Scale Free Graph モデルに関する研究.” Web. 19 Jan 2021.
Note: this citation may be lacking information needed for this citation format:
No year of publication.
Vancouver:
森本 . 時系列データに基づいた Scale Free Graph モデルに関する研究. [Internet] [Thesis]. Japan Advanced Institute of Science and Technology / 北陸先端科学技術大学院大学; [cited 2021 Jan 19].
Available from: http://hdl.handle.net/10119/8101.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
No year of publication.
Council of Science Editors:
森本 . 時系列データに基づいた Scale Free Graph モデルに関する研究. [Thesis]. Japan Advanced Institute of Science and Technology / 北陸先端科学技術大学院大学; Available from: http://hdl.handle.net/10119/8101
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
No year of publication.
12.
Arvind, N R.
Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -.
Degree: Mathematical Science, 2010, INFLIBNET
URL: http://shodhganga.inflibnet.ac.in/handle/10603/4726
► This thesis deals mainly with two related coloring problems ? forbidden subgraph colorings and oriented colorings. The former deals with proper colorings of vertices or…
(more)
▼ This thesis deals mainly with two related coloring
problems ? forbidden subgraph colorings and oriented colorings. The
former deals with proper colorings of vertices or edges of a graph
with constraints on the union of color classes. A well-known
example is the acyclic vertex coloring in which we require a proper
coloring such that the union of any two color classes is acyclic.
Other wellstudied examples include the acyclic edge coloring and
star coloring. Our focus in this thesis is a generalization of
these special types of colorings. Oriented coloring deals with
colorings of oriented graphs (directed graphs obtained by orienting
each edge of a simple undirected graph). Specifically, an oriented
coloring is a homomorphism to an oriented graph, the vertices of
the target graph being considered as the colors assigned to the
vertices of the source graph. For both of these problems, we want
to find good upper bounds for the number of colors required for
such colorings. In this thesis, we find upper bounds for forbidden
subgraph chromatic numbers in terms of the maximum degree. For the
union of two color classes, we show the asymptotic tightness of our
bounds by a probabilistic contstruction. We then show that the
oriented chromatic number of a graph can be bounded in terms of the
forbidden subgraph chromatic numbers. In conjunction with our
afore-mentioned results, this allowed us to prove improved bounds
on oriented chromatic numbers of graphs on surfaces. Specifically,
we obtained the following results: ? Given a family F of connected
graphs each having at least m edges, the vertices of any graph
ofmaximum degree _ can be properly colored using O(_1+ 1
mand#8722;1 ) colors so that in the union of any 2 color classes,
there is no copy of H for any H and#8712; F. ? Any graph of genus g
has oriented chromatic number at most 2g1/2+o(1) . We also consider
edge colorings of graphs with restrictions on the union of color
classes. While edge colorings can simply be considered as vertex
colorings of the line graph.
Bibilography p.95-101
Advisors/Committee Members: Balasubramanian R, Subramanian, C R.
Subjects/Keywords: Graphs; Graphs dimensions; Graphs colorings
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Arvind, N. R. (2010). Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -. (Thesis). INFLIBNET. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/4726
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Arvind, N R. “Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -.” 2010. Thesis, INFLIBNET. Accessed January 19, 2021.
http://shodhganga.inflibnet.ac.in/handle/10603/4726.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Arvind, N R. “Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -.” 2010. Web. 19 Jan 2021.
Vancouver:
Arvind NR. Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -. [Internet] [Thesis]. INFLIBNET; 2010. [cited 2021 Jan 19].
Available from: http://shodhganga.inflibnet.ac.in/handle/10603/4726.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Arvind NR. Forbidden subgraph colorings, oriented colorings and
intersection dimensions of graphs; -. [Thesis]. INFLIBNET; 2010. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/4726
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Arizona State University
13.
Das, Sayantan.
Interfacial and Electrode Modifications in P3HT:PC61BM based
Organic Solar Cells: Devices, Processing and
Characterization.
Degree: Chemistry, 2015, Arizona State University
URL: http://repository.asu.edu/items/34828
► The inexorable upsurge in world’s energy demand has steered the search for newer renewable energy sources and photovoltaics seemed to be one of the best…
(more)
▼ The inexorable upsurge in world’s energy demand has
steered the search for newer renewable energy sources and
photovoltaics seemed to be one of the best alternatives for energy
production. Among the various photovoltaic technologies that
emerged, organic/polymer photovoltaics based on solution processed
bulk-heterojunctions (BHJ) of semiconducting polymers has gained
serious attention owing to the use of inexpensive light-weight
materials, exhibiting high mechanical flexibility and compatibility
with low temperature roll-to-roll manufacturing techniques on
flexible substrates. The most widely studied material to date is
the blend of regioregular P3HT and PC61BM used as donor and
acceptor materials. The object of this study was to investigate and
improve the performance/stability of the organic solar cells by use
of inexpensive materials. In an attempt to enhance the efficiency
of organic solar cells, we have demonstrated the use of
hexamethyldisilazane (HMDS) modified indium tin oxide (ITO)
electrode in bulk heterojunction solar cell structure The device
studies showed a significant enhancement in the short-circuit
current as well as in the shunt resistance on use of the
hexamethyldisilazane (HMDS) layer. In another approach a p-type CuI
hole-transport layer was utilized that could possibly replace the
acidic PEDOT:PSS layer in the fabrication of high-efficiency solar
cells. The device optimization was done by varying the
concentration of CuI in the precursor solution which played an
important role in the efficiency of the solar cell devices.
Recently a substantial amount of research has been focused on
identifying suitable interfacial layers in organic solar cells
which has efficient charge transport properties. It was illustrated
that a thin layer of silver oxide interfacial layer showed a 28%
increase in power conversion efficiency in comparison to that of
the control cell. The optoelectronic properties and morphological
features of indium-free ZnO/Ag/MoOx electrodes was also studied.
Organic solar cells on these composite electrodes revealed good
optical and electrical properties, making them a promising
alternative indium free and PEDOT:PSS-free organic solar cells.
Lastly, inverted solar cells utilizing zinc oxide and yttrium doped
zinc oxide electron transport was also created and their device
properties revealed that optimum annealing conditions and yttrium
doping was essential to obtain high efficiency solar
cells.
Subjects/Keywords: Chemistry; Materials Science; copper iodide hole transport layer; HMDS modified ITO; ITO free electrode; organic solar cells; P3HT:PC61BM
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Das, S. (2015). Interfacial and Electrode Modifications in P3HT:PC61BM based
Organic Solar Cells: Devices, Processing and
Characterization. (Doctoral Dissertation). Arizona State University. Retrieved from http://repository.asu.edu/items/34828
Chicago Manual of Style (16th Edition):
Das, Sayantan. “Interfacial and Electrode Modifications in P3HT:PC61BM based
Organic Solar Cells: Devices, Processing and
Characterization.” 2015. Doctoral Dissertation, Arizona State University. Accessed January 19, 2021.
http://repository.asu.edu/items/34828.
MLA Handbook (7th Edition):
Das, Sayantan. “Interfacial and Electrode Modifications in P3HT:PC61BM based
Organic Solar Cells: Devices, Processing and
Characterization.” 2015. Web. 19 Jan 2021.
Vancouver:
Das S. Interfacial and Electrode Modifications in P3HT:PC61BM based
Organic Solar Cells: Devices, Processing and
Characterization. [Internet] [Doctoral dissertation]. Arizona State University; 2015. [cited 2021 Jan 19].
Available from: http://repository.asu.edu/items/34828.
Council of Science Editors:
Das S. Interfacial and Electrode Modifications in P3HT:PC61BM based
Organic Solar Cells: Devices, Processing and
Characterization. [Doctoral Dissertation]. Arizona State University; 2015. Available from: http://repository.asu.edu/items/34828
Australian National University
14.
Rezvani, Mojtaba.
Community Structure in Large-Scale Complex Networks
.
Degree: 2019, Australian National University
URL: http://hdl.handle.net/1885/187032
► Vertices in complex networks can be grouped into communities, where vertices inside communities are densely connected to each other and vertices from one community are…
(more)
▼ Vertices in complex networks can be grouped into communities,
where vertices inside communities are densely connected to each
other and vertices from one community are sparsely connected to
vertices in other communities. This is the so-called community
structure in complex networks. Identifying the community
structure of networks has many applications, ranging from data
mining, webpage clustering and market- ing to extracting proteins
with the same functionality in protein-protein-interaction
networks and beyond.
This thesis addresses a number of the primary problems
surrounding community structure in large-scale networks. These
problems generally revolve around two of the principal challenges
of the area, accuracy and soundness of modelling and scala-
bility to real-world networks. The problems include identifying
top-k structural hole spanners, detecting the hierarchy of
communities, detecting overlapping communi- ties, and community
search in large-scale complex networks. The thesis formally de-
fines the cohesive hierarchies of communities in complex
networks. Since scalability is a major challenge for cohesive
hierarchical community detection, the thesis incor- porates a
network sparsification technique to leverage the network size and
finds co- hesive hierarchies of communities in large-scale
complex networks. The problem of identifying top-k structural
hole spanners is formally defined in this thesis and several
scalable algorithms have been presented for this problem.
Furthermore, the thesis delves into the problem of overlapping
community detection and proposes an accu- rate fitness metric to
find overlapping communities in large-scale complex networks. The
thesis finally studies the problem of community search and
introduces a new al- gorithm for community search in complex
networks.
The thesis develops novel models, algorithms, and evaluation
measures for these problems, and presents the experimental
results of these algorithms using real-world datasets, which
outperform considerably on the scalability and accuracy of the
state of the art, in several cases.
Subjects/Keywords: complex networks;
community structure;
community detection;
community search;
overlapping community detection;
structural hole spanners;
social networks;
large-scale networks;
large-scale graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Rezvani, M. (2019). Community Structure in Large-Scale Complex Networks
. (Thesis). Australian National University. Retrieved from http://hdl.handle.net/1885/187032
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Rezvani, Mojtaba. “Community Structure in Large-Scale Complex Networks
.” 2019. Thesis, Australian National University. Accessed January 19, 2021.
http://hdl.handle.net/1885/187032.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Rezvani, Mojtaba. “Community Structure in Large-Scale Complex Networks
.” 2019. Web. 19 Jan 2021.
Vancouver:
Rezvani M. Community Structure in Large-Scale Complex Networks
. [Internet] [Thesis]. Australian National University; 2019. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/1885/187032.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Rezvani M. Community Structure in Large-Scale Complex Networks
. [Thesis]. Australian National University; 2019. Available from: http://hdl.handle.net/1885/187032
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
McMaster University
15.
Mhaskar, Neerja.
A Generalization of Square-free Strings.
Degree: PhD, 2016, McMaster University
URL: http://hdl.handle.net/11375/20492
► Our research is in the general area of String Algorithms and Combinatorics on Words. Specifically, we study a generalization of square-free strings, shuffle properties of…
(more)
▼ Our research is in the general area of String Algorithms and Combinatorics on Words. Specifically, we study a generalization of square-free strings, shuffle properties of strings, and formalizing the reasoning about finite strings.
The existence of infinitely long square-free strings (strings with no adjacent repeating word blocks) over a three (or more) letter finite set (referred to as Alphabet) is a well-established result. A natural generalization of this problem is that only subsets of the alphabet with predefined cardinality are available, while selecting symbols of the square-free string. This problem has been studied by several authors, and the lowest possible bound on the cardinality of the subset given is four. The problem remains open for subset size three and we investigate this question. We show that square-free strings exist in several specialized cases of the problem and propose approaches to solve the problem, ranging from patterns in strings to Proof Complexity. We also study the shuffle property (analogous to shuffling a deck of cards labeled with symbols) of strings, and explore the relationship between string shuffle and graphs, and show that large classes of graphs can be represented with special type of strings.
Finally, we propose a theory of strings, that formalizes the reasoning about finite strings. By engaging in this line of research, we hope to bring the richness of the advanced field of Proof Complexity to Stringology.
Thesis
Doctor of Philosophy (PhD)
Advisors/Committee Members: Soltys, Michael, Computing and Software.
Subjects/Keywords: Strings; Repetitions; Square-free; Thue Morphisms; Formalism for strings; Proof Complexity; String Algorithms; String shuffle; Graphs and string shuffle
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Mhaskar, N. (2016). A Generalization of Square-free Strings. (Doctoral Dissertation). McMaster University. Retrieved from http://hdl.handle.net/11375/20492
Chicago Manual of Style (16th Edition):
Mhaskar, Neerja. “A Generalization of Square-free Strings.” 2016. Doctoral Dissertation, McMaster University. Accessed January 19, 2021.
http://hdl.handle.net/11375/20492.
MLA Handbook (7th Edition):
Mhaskar, Neerja. “A Generalization of Square-free Strings.” 2016. Web. 19 Jan 2021.
Vancouver:
Mhaskar N. A Generalization of Square-free Strings. [Internet] [Doctoral dissertation]. McMaster University; 2016. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/11375/20492.
Council of Science Editors:
Mhaskar N. A Generalization of Square-free Strings. [Doctoral Dissertation]. McMaster University; 2016. Available from: http://hdl.handle.net/11375/20492
University of Dayton
16.
Krishnamurthy, Chandra Mohan.
The Maximum Induced Matching Problem for Some Subclasses of
Weakly Chordal Graphs.
Degree: Master of Computer Science (M.C.S.), Computer Science, 2009, University of Dayton
URL: http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006
► An induced matching in a graph is a set of edges such that no two edges in the set are joined by any third edge…
(more)
▼ An induced matching in a graph is a set of edges such
that no two edges in the set are joined by any third edge of the
graph. An induced matching is maximum (MIM) if the number of edges
in it is the largest among all possible induced matchings. It is
known that finding the size of MIM in a graph is NP-hard
even if
the graph is bipartite. It is also known that the size of MIM in a
chordal graph or in a weakly chordal graph can be computed in
polynomial time. Specifically, the size of MIM can be computed in
linear time for a chordal graph and in O(m
3)
time for a weaklychordal graph. This work demonstrates some
algorithms for the maximum inducedmatching problem with complexity
better than O(m
3) for some subclasses of
weaklychordal
graphs. In particular, we show that the maximum
induced matching problemcan be solved on hhd-
free graphs in
O(m
2) time. Further, for two subclasses of
hhd-
free graphs, we show that the problem can be solved in better
time than O(m
2). The classes of
graphs that
we consider are either more general than chordal
graphs or are a
restriction of chordal bipartite
graphs.
Advisors/Committee Members: Sritharan, R (Advisor).
Subjects/Keywords: Computer Science; Maximum induced matching; Induced matching; hhd-free graphs; chordal graphs; weakly chordal graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Krishnamurthy, C. M. (2009). The Maximum Induced Matching Problem for Some Subclasses of
Weakly Chordal Graphs. (Masters Thesis). University of Dayton. Retrieved from http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006
Chicago Manual of Style (16th Edition):
Krishnamurthy, Chandra Mohan. “The Maximum Induced Matching Problem for Some Subclasses of
Weakly Chordal Graphs.” 2009. Masters Thesis, University of Dayton. Accessed January 19, 2021.
http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006.
MLA Handbook (7th Edition):
Krishnamurthy, Chandra Mohan. “The Maximum Induced Matching Problem for Some Subclasses of
Weakly Chordal Graphs.” 2009. Web. 19 Jan 2021.
Vancouver:
Krishnamurthy CM. The Maximum Induced Matching Problem for Some Subclasses of
Weakly Chordal Graphs. [Internet] [Masters thesis]. University of Dayton; 2009. [cited 2021 Jan 19].
Available from: http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006.
Council of Science Editors:
Krishnamurthy CM. The Maximum Induced Matching Problem for Some Subclasses of
Weakly Chordal Graphs. [Masters Thesis]. University of Dayton; 2009. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=dayton1262624006
NSYSU
17.
Fu, Chien-jung.
Design of Various VLSI Sorting Accelerator Architectures.
Degree: Master, Computer Science and Engineering, 2009, NSYSU
URL: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0831109-115655
► In this thesis, various designs of VLSI sorter architectures are proposed. This thesis first presents a baseline serial sorter architecture built on a central memory…
(more)
▼ In this thesis, various designs of VLSI sorter architectures are proposed. This thesis first presents a baseline serial sorter architecture built on a central memory module equipped with a single compare-and-swap (C&S) functional unit. A dedicated low-cost address generation circuit which controls the order of data accesses and C&S operation in order to support sorting of data sequences with any length is proposed. By exploring the bit-permutation technique to create the access orders suitable for different C&S steps, the address generator can be built by only two adders and three shifters plus some control circuits, and consumes only about 1K gates. Next, this thesis also proposes a two-bank memory architecture to reduce the required memory ports from four to two such that the sorter memory can be realized by on-chip SRAM blocks. Our experimental results show that the overall silicon cost can be reduced by more than 56% for the sorter circuit which can sort the data sequence of length up to 1024.
In addition to the serial sorter architecture, this thesis further proposes three possible parallel sorter architectures including the pipeline sorter, cascade sorter, and block sorter. Among these three architectures, the pipeline sorter can deliver the best throughput although it can be used only for fixed-length data sequences. On the other hand, the block sorter is the most flexible design suitable for sequences with variable length. It is designed based on the block-level
even-odd merge sort algorithm. It significantly outperforms the previous block sorter design by using more efficient algorithm, architectural pipelining, and better block C&S(BC&S) unit which can realize separate pre-sort and merge processes efficiently. Our implementation results show that by using the 0.18um technology, the core size of the proposed sorter with block-size of four is about 0.509mm2, and can sorting a 1024-point sequence within 32.84us.
Advisors/Committee Members: Chuen-Yau Chen (chair), Yun-Nan Chang (committee member), Shiann-Rong Kuang (chair).
Subjects/Keywords: Sorter; Odd-Even merge sort
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Fu, C. (2009). Design of Various VLSI Sorting Accelerator Architectures. (Thesis). NSYSU. Retrieved from http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0831109-115655
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Fu, Chien-jung. “Design of Various VLSI Sorting Accelerator Architectures.” 2009. Thesis, NSYSU. Accessed January 19, 2021.
http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0831109-115655.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Fu, Chien-jung. “Design of Various VLSI Sorting Accelerator Architectures.” 2009. Web. 19 Jan 2021.
Vancouver:
Fu C. Design of Various VLSI Sorting Accelerator Architectures. [Internet] [Thesis]. NSYSU; 2009. [cited 2021 Jan 19].
Available from: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0831109-115655.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Fu C. Design of Various VLSI Sorting Accelerator Architectures. [Thesis]. NSYSU; 2009. Available from: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0831109-115655
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
18.
Sibel, Jean-Christophe.
Region-based approximation to solve inference in loopy factor graphs : decoding LDPC codes by the Generalized Belief Propagation : Approximation basée régions pour résoudre l'inférence dans les graphes factoriels à boucles : application au décodage des codes LDPC par le Generalized Belief Propagation.
Degree: Docteur es, STIC (sciences et technologies de l'information et de la communication) - Cergy, 2013, Cergy-Pontoise
URL: http://www.theses.fr/2013CERG0629
► Dans cette thèse, nous étudions le problème de l'inférence bayésienne dans les graphes factoriels, en particulier les codes LDPC, quasiment résolus par les algorithmes de…
(more)
▼ Dans cette thèse, nous étudions le problème de l'inférence bayésienne dans les graphes factoriels, en particulier les codes LDPC, quasiment résolus par les algorithmes de message-passing. Nous réalisons en particulier une étude approfondie du Belief Propagation (BP) dont la question de la sous-optimalité est soulevée dans le cas où le graphe factoriel présente des boucles. A partir de l'équivalence entre le BP et l'approximation de Bethe en physique statistique qui se généralise à l'approximation basée régions, nous détaillons le Generalized Belief Propagation (GBP), un algorithme de message-passing entre des clusters du graphe factoriel. Nous montrons par des expériences que le GBP surpasse le BP dans les cas où le clustering est réalisé selon les structures topologiques néfastes qui empêchent le BP de bien décoder, à savoir les trapping sets. Au-delà de l'étude des performances en termes de taux d'erreur, nous confrontons les deux algorithmes par rapport à leurs dynamiques face à des événements d'erreur non triviaux, en particulier lorsqu'ils présentent des comportements chaotiques. Par des estimateurs classiques et originaux, nous montrons que l'algorithme du GBP peut dominer l'algorithme du BP.
This thesis addresses the problem of inference in factor graphs, especially the LDPC codes, almost solved by message-passing algorithms. In particular, the Belief Propagation algorithm (BP) is investigated as a particular message-passing algorithm whose suboptimality is discussed in the case where the factor graph has a loop-like topology. From the equivalence between the BP and the Bethe approximation in statistical physics that is generalized to the region-based approximation, is detailed the Generalized Belief Propagation algorithm (GBP), a message-passing algorithm between clusters of the factor graph. It is experimentally shown to surpass the BP in the cases where the clustering deals with the harmful topological structures that prevents the BP from rightly decoding any LDPC code, namely the trapping sets. We do not only confront the BP and the GBP algorithms according to their performance from the point of view of the channel coding with the error-rate, but also according to their dynamical behaviors for non-trivial error-events for which both algorithms can exhibit chaotic beahviors. By means of classical and original dynamical quantifiers, it is shown that the GBP algorithm can overcome the BP algorithm.
Advisors/Committee Members: Declercq, David (thesis director).
Subjects/Keywords: Graphe factoriel; Ldpc; Énergie libre variationnelle; Approximation basée régions; Trapping sets; Chaos; Factor graphs; Ldpc; Variational free energy; Region-based approximation; Trapping sets; Chaos
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Sibel, J. (2013). Region-based approximation to solve inference in loopy factor graphs : decoding LDPC codes by the Generalized Belief Propagation : Approximation basée régions pour résoudre l'inférence dans les graphes factoriels à boucles : application au décodage des codes LDPC par le Generalized Belief Propagation. (Doctoral Dissertation). Cergy-Pontoise. Retrieved from http://www.theses.fr/2013CERG0629
Chicago Manual of Style (16th Edition):
Sibel, Jean-Christophe. “Region-based approximation to solve inference in loopy factor graphs : decoding LDPC codes by the Generalized Belief Propagation : Approximation basée régions pour résoudre l'inférence dans les graphes factoriels à boucles : application au décodage des codes LDPC par le Generalized Belief Propagation.” 2013. Doctoral Dissertation, Cergy-Pontoise. Accessed January 19, 2021.
http://www.theses.fr/2013CERG0629.
MLA Handbook (7th Edition):
Sibel, Jean-Christophe. “Region-based approximation to solve inference in loopy factor graphs : decoding LDPC codes by the Generalized Belief Propagation : Approximation basée régions pour résoudre l'inférence dans les graphes factoriels à boucles : application au décodage des codes LDPC par le Generalized Belief Propagation.” 2013. Web. 19 Jan 2021.
Vancouver:
Sibel J. Region-based approximation to solve inference in loopy factor graphs : decoding LDPC codes by the Generalized Belief Propagation : Approximation basée régions pour résoudre l'inférence dans les graphes factoriels à boucles : application au décodage des codes LDPC par le Generalized Belief Propagation. [Internet] [Doctoral dissertation]. Cergy-Pontoise; 2013. [cited 2021 Jan 19].
Available from: http://www.theses.fr/2013CERG0629.
Council of Science Editors:
Sibel J. Region-based approximation to solve inference in loopy factor graphs : decoding LDPC codes by the Generalized Belief Propagation : Approximation basée régions pour résoudre l'inférence dans les graphes factoriels à boucles : application au décodage des codes LDPC par le Generalized Belief Propagation. [Doctoral Dissertation]. Cergy-Pontoise; 2013. Available from: http://www.theses.fr/2013CERG0629
Université de Grenoble
19.
Morel, Gregory.
Stabilité et coloration des graphes sans P5 : Independent sets and coloring in P5-free graphs.
Degree: Docteur es, Mathématiques et informatique, 2011, Université de Grenoble
URL: http://www.theses.fr/2011GRENM042
► La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des…
(more)
▼ La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielle.
The class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A.
Advisors/Committee Members: Szigeti, Zoltán (thesis director), Maffray, Frédéric (thesis director).
Subjects/Keywords: Théorie des graphes; Optimisation combinatoire; Stabilité; Coloration; Graphes sans P5; Graph Theory; Combinatorial optimization; Maximum Independent Set problem; Coloring; P5-free graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Morel, G. (2011). Stabilité et coloration des graphes sans P5 : Independent sets and coloring in P5-free graphs. (Doctoral Dissertation). Université de Grenoble. Retrieved from http://www.theses.fr/2011GRENM042
Chicago Manual of Style (16th Edition):
Morel, Gregory. “Stabilité et coloration des graphes sans P5 : Independent sets and coloring in P5-free graphs.” 2011. Doctoral Dissertation, Université de Grenoble. Accessed January 19, 2021.
http://www.theses.fr/2011GRENM042.
MLA Handbook (7th Edition):
Morel, Gregory. “Stabilité et coloration des graphes sans P5 : Independent sets and coloring in P5-free graphs.” 2011. Web. 19 Jan 2021.
Vancouver:
Morel G. Stabilité et coloration des graphes sans P5 : Independent sets and coloring in P5-free graphs. [Internet] [Doctoral dissertation]. Université de Grenoble; 2011. [cited 2021 Jan 19].
Available from: http://www.theses.fr/2011GRENM042.
Council of Science Editors:
Morel G. Stabilité et coloration des graphes sans P5 : Independent sets and coloring in P5-free graphs. [Doctoral Dissertation]. Université de Grenoble; 2011. Available from: http://www.theses.fr/2011GRENM042
Uniwersytet im. Adama Mickiewicza w Poznaniu
20.
Antoniuk, Sylwia.
Silne funkcje progowe dla pewnych własności grup losowych
.
Degree: 2014, Uniwersytet im. Adama Mickiewicza w Poznaniu
URL: http://hdl.handle.net/10593/10974
► Rozprawa poświęcona jest badaniu ewolucji losowej grupy trójkątnej, zdefiniowanej jako grupa zadana losową prezentacją grupy z relatorami długości trzy. W pracy stosujemy model dwumianowy takiej…
(more)
▼ Rozprawa poświęcona jest badaniu ewolucji losowej grupy trójkątnej, zdefiniowanej jako grupa zadana losową prezentacją grupy z relatorami długości trzy. W pracy stosujemy model dwumianowy takiej grupy, w którym każde słowo o długości trzy zaliczane jest do zbioru relatorów niezależnie, z zadanym prawdopodobieństwem p. Głównym obiektem naszych badań są funkcje progowe dla takich własności grup, jak własność bycia grupą wolną, własność Kazhdana (T), hiperboliczność i własność trywializowania się grupy. Zaprezentowane w rozprawie twierdzenia w istotny sposób wzmacniają znane wyniki i oszacowania; w szczególności pokazano, że szereg własności grupowych ma silne funkcje progowe. W rozprawie opisano również nieznany dotąd okres w ewolucji losowej grupy trójkątnej, w którym grupa ta nie jest grupą wolną i jednocześnie nie ma własności (T). Podstawową metodą badania grup losowych stosowaną w rozprawie jest sprowadzenie własności grup losowych do własności odpowiednio zdefiniowanych grafów i hipergrafów losowych.
Advisors/Committee Members: Łuczak, Tomasz. Promotor (advisor).
Subjects/Keywords: grupy losowe;
random groups;
funkcje progowe;
threshold functions;
grafy losowe;
random graphs;
grupa wolna;
free groups;
własność (T) Kazhdana;
Kazhdan's property (T)
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Antoniuk, S. (2014). Silne funkcje progowe dla pewnych własności grup losowych
. (Doctoral Dissertation). Uniwersytet im. Adama Mickiewicza w Poznaniu. Retrieved from http://hdl.handle.net/10593/10974
Chicago Manual of Style (16th Edition):
Antoniuk, Sylwia. “Silne funkcje progowe dla pewnych własności grup losowych
.” 2014. Doctoral Dissertation, Uniwersytet im. Adama Mickiewicza w Poznaniu. Accessed January 19, 2021.
http://hdl.handle.net/10593/10974.
MLA Handbook (7th Edition):
Antoniuk, Sylwia. “Silne funkcje progowe dla pewnych własności grup losowych
.” 2014. Web. 19 Jan 2021.
Vancouver:
Antoniuk S. Silne funkcje progowe dla pewnych własności grup losowych
. [Internet] [Doctoral dissertation]. Uniwersytet im. Adama Mickiewicza w Poznaniu; 2014. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/10593/10974.
Council of Science Editors:
Antoniuk S. Silne funkcje progowe dla pewnych własności grup losowych
. [Doctoral Dissertation]. Uniwersytet im. Adama Mickiewicza w Poznaniu; 2014. Available from: http://hdl.handle.net/10593/10974
21.
Tian, Tao.
Degree Conditions for Hamiltonian Properties of Claw-free Graphs.
Degree: 2018, Ipskamp Printing
URL: https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html
;
urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f
;
47d10092-82bd-4a30-9cb0-4bac2daa563f
;
10.3990/1.9789036546102
;
urn:isbn:978-90-365-4610-2
;
urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f
;
https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html
► This thesis contains many new contributions to the field of hamiltonian graph theory, a very active subfield of graph theory. In particular, we have obtained…
(more)
▼ This thesis contains many new contributions to the field of hamiltonian graph theory, a very active subfield of graph theory. In particular, we have obtained new sufficient minimum degree and degree sum conditions to guarantee that the
graphs satisfying these conditions, or their line
graphs, admit a Hamilton cycle (or a Hamilton path), unless they have a small order or they belong to well-defined classes of exceptional
graphs. Here, a Hamilton cycle corresponds to traversing the vertices and edges of the graph in such a way that all their vertices are visited exactly once, and we return to our starting vertex (similarly, a Hamilton path reflects a similar way of traversing the graph, but without the last restriction, so we might terminate at a different vertex). In Chapter 1, we presented an introduction to the topics of this thesis together with Ryjáček’s closure for claw-
free graphs, Catlin’s reduction method, and the reduction of the core of a graph. In Chapter 2, we found the best possible bounds for the minimum degree condition and the minimum degree sums condition of adjacent vertices for traceability of 2-connected claw-
free graph, respectively. In addition, we decreased these lower bounds with one family of well characterized exceptional
graphs. In Chapter 3, we extended recent results about the conjecture of Benhocine et al. and results about the conjecture of Z.-H Chen and H.-J Lai. In Chapters 4, 5 and 6, we have successfully tried to unify and extend several existing results involving the degree and neighborhood conditions for the hamiltonicity and traceability of 2-connected claw-
free graphs. Throughout this thesis, we have investigated the existence of Hamilton cycles and Hamilton paths under different types of degree and neighborhood conditions, including minimum degree conditions, minimum degree sum conditions on adjacent pairs of vertices, minimum degree sum conditions over all independent sets of t vertices of a graph, minimum cardinality conditions on the neighborhood union over all independent sets of t vertices of a graph, as well minimum cardinality conditions on the neighborhood union over all t vertex sets of a graph. Despite our new contributions, many problems and conjectures remain unsolved.
Advisors/Committee Members: Broersma, Hajo.
Subjects/Keywords: Degree conditions; Hamilton cycle; Hamilton path; Closure; Reduction; Claw-free graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Tian, T. (2018). Degree Conditions for Hamiltonian Properties of Claw-free Graphs. (Doctoral Dissertation). Ipskamp Printing. Retrieved from https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; 47d10092-82bd-4a30-9cb0-4bac2daa563f ; 10.3990/1.9789036546102 ; urn:isbn:978-90-365-4610-2 ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html
Chicago Manual of Style (16th Edition):
Tian, Tao. “Degree Conditions for Hamiltonian Properties of Claw-free Graphs.” 2018. Doctoral Dissertation, Ipskamp Printing. Accessed January 19, 2021.
https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; 47d10092-82bd-4a30-9cb0-4bac2daa563f ; 10.3990/1.9789036546102 ; urn:isbn:978-90-365-4610-2 ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html.
MLA Handbook (7th Edition):
Tian, Tao. “Degree Conditions for Hamiltonian Properties of Claw-free Graphs.” 2018. Web. 19 Jan 2021.
Vancouver:
Tian T. Degree Conditions for Hamiltonian Properties of Claw-free Graphs. [Internet] [Doctoral dissertation]. Ipskamp Printing; 2018. [cited 2021 Jan 19].
Available from: https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; 47d10092-82bd-4a30-9cb0-4bac2daa563f ; 10.3990/1.9789036546102 ; urn:isbn:978-90-365-4610-2 ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html.
Council of Science Editors:
Tian T. Degree Conditions for Hamiltonian Properties of Claw-free Graphs. [Doctoral Dissertation]. Ipskamp Printing; 2018. Available from: https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; 47d10092-82bd-4a30-9cb0-4bac2daa563f ; 10.3990/1.9789036546102 ; urn:isbn:978-90-365-4610-2 ; urn:nbn:nl:ui:28-47d10092-82bd-4a30-9cb0-4bac2daa563f ; https://research.utwente.nl/en/publications/degree-conditions-for-hamiltonian-properties-of-clawfree-graphs(47d10092-82bd-4a30-9cb0-4bac2daa563f).html
22.
Mozes, Shay.
Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs.
Degree: PhD, Computer Science, 2013, Brown University
URL: https://repository.library.brown.edu/studio/item/bdr:320482/
► Large graphs are ubiquitous in many diverse fields ranging from sociology and economics to biology and engineering. Applications in numerous areas such as transportation, geographical…
(more)
▼ Large
graphs are ubiquitous in many diverse fields
ranging from sociology and economics to biology and engineering.
Applications in numerous areas such as transportation, geographical
routing, computer vision and VLSI design involve solving
optimization problems on large planar
graphs. The sheer growth in
the number and size of available data sets drives a need to design
optimization algorithms that are not merely efficient in the
qualitative sense that their computational resource consumption is
polynomial in the size of the input, but in the stronger
quantitative sense that the amount of required resources
(specifically, running time and space) is as close to linear as
possible.
In this thesis we study the combinatorial structural
properties of directed planar
graphs, and exploit these properties
to devise efficient algorithms for shortest-path and maximum-flow
problems in such
graphs. Among the results we present are:
- A linear-space algorithm for the shortest-path problem in
directed planar
graphs with real (positive and negative) arc
lengths that runs in near-linear time. Our algorithm is more
efficient and conceptually simpler than previously known algorithms
for this problem.
- Data structures for efficiently reporting exact distances
in directed planar
graphs (distance oracles) with significantly
improved space-to-query-time ratio over previously known exact
distance oracles.
- A near-linear time algorithm for computing a maximum flow
in directed planar
graphs with multiple sources and sinks. This
problem has been open for more than 20 years. No planarity
exploiting algorithm for the problem was previously known. Our
algorithm is significantly faster than previous algorithms for this
problem.
These problems, and the tools and techniques used in solving
them, are interrelated.
Advisors/Committee Members: Klein, Philip (Director), Erickson, Jeff (Reader), Kelner, Jonathan (Reader), Mathieu, Claire (Reader).
Subjects/Keywords: planar graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Mozes, S. (2013). Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs. (Doctoral Dissertation). Brown University. Retrieved from https://repository.library.brown.edu/studio/item/bdr:320482/
Chicago Manual of Style (16th Edition):
Mozes, Shay. “Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs.” 2013. Doctoral Dissertation, Brown University. Accessed January 19, 2021.
https://repository.library.brown.edu/studio/item/bdr:320482/.
MLA Handbook (7th Edition):
Mozes, Shay. “Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs.” 2013. Web. 19 Jan 2021.
Vancouver:
Mozes S. Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs. [Internet] [Doctoral dissertation]. Brown University; 2013. [cited 2021 Jan 19].
Available from: https://repository.library.brown.edu/studio/item/bdr:320482/.
Council of Science Editors:
Mozes S. Efficient Algorithms for Shortest-Path and Maximum-Flow
Problems in Planar Graphs. [Doctoral Dissertation]. Brown University; 2013. Available from: https://repository.library.brown.edu/studio/item/bdr:320482/
23.
Camarero Coterillo, Cristobal.
Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.
Degree: 2015, Universidad de Cantabria
URL: http://hdl.handle.net/10902/6542
► ABSTRACT: The topology of a interconnection network is the graph of its routers. The topologies that are being currently used in large supercomputers can be…
(more)
▼ ABSTRACT: The topology of a interconnection network is the graph of its routers. The topologies that are being currently used in large supercomputers can be classified into two families: the ones that use routers with moderate radix and the ones using high-radix routers. The objective of this thesis is to define topologies for both families that exhibit better properties than the actual ones.
Examples of moderate degree machines are the Cray XK7, the K computer and the Blue Gene/Q, whose topologies are tori. In this thesis the lattice
graphs are proposed. They are variant of tori with reduced distances and which can be symmetric for sizes in which the tori is forced to be asymmetric.
Among the most used topologies for the family of high-radix routers there are the Clos networks, and more recently, the dragonfly networks. This thesis focuses on dragonfly networks. In this thesis, it is explained how Hamming
graphs can be seen as a dragonfly with large global trunking and that some properties of the Hamming
graphs can be extrapolated to dragonflies.
The problem of finding lattice
graphs with optimal distance properties is actually equivalent to the problem of finding good codes over the Lee space. In this thesis several quasi-perfect codes are built, which can then be seen as nearly optimal lattice
graphs. They include quasi-perfect codes for arbitrarily large dimensions that reach half the density of the density of potential perfect Lee.
Advisors/Committee Members: Martínez Fernández, María del Carmen (advisor), Universidad de Cantabria (other).
Subjects/Keywords: Graphs
…Afterwards, it is seen that indeed the
Hamming graphs allow for deadlock-free routing without VCs… …brings the
definition of lattice graphs, which actually contains all Cayley graphs over Abelian… …used
in crystallography. When these are used to define lattice graphs, good properties are… …machines. From the properties of these crystal lattice graphs the symmetry is
very notable; it is… …obtained that symmetric lattice graphs have better performance than
the asymmetric ones. This…
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Camarero Coterillo, C. (2015). Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. (Doctoral Dissertation). Universidad de Cantabria. Retrieved from http://hdl.handle.net/10902/6542
Chicago Manual of Style (16th Edition):
Camarero Coterillo, Cristobal. “Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.” 2015. Doctoral Dissertation, Universidad de Cantabria. Accessed January 19, 2021.
http://hdl.handle.net/10902/6542.
MLA Handbook (7th Edition):
Camarero Coterillo, Cristobal. “Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.” 2015. Web. 19 Jan 2021.
Vancouver:
Camarero Coterillo C. Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. [Internet] [Doctoral dissertation]. Universidad de Cantabria; 2015. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/10902/6542.
Council of Science Editors:
Camarero Coterillo C. Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. [Doctoral Dissertation]. Universidad de Cantabria; 2015. Available from: http://hdl.handle.net/10902/6542
University of Florida
24.
Alipanahi Ramandi, Bahareh.
Variants and Applications of Colored De Bruijn Graphs.
Degree: PhD, Computer Science - Computer and Information Science and Engineering, 2020, University of Florida
URL: https://ufdc.ufl.edu/UFE0056439
► Colored de Bruijn graphs,extensions of the de Bruijn graphs are fundamental data structures for the analysis of high-throughput sequencing data. Although colored de Bruin graphs…
(more)
▼ Colored de Bruijn
graphs,extensions of the de Bruijn
graphs are fundamental data structures for the analysis of high-throughput sequencing data. Although colored de Bruin
graphs were designed for the detection of genetic variations among individuals of a population, they also can be helpful in disentangling the De Bruijn
graphs. One of the challenges of colored De Bruijn
graphs is lack of read coherence, meaning the correspondences between k-mers and reads are lost. Consequently, colored de Bruijn
graphs are prone to generating inaccurate contigs. Moreover, to be applicable to population-scale cohorts and to be able to dynamically add or remove samples to the study, it is essential to build and store colored de Bruijn
graphs in a space and time-efficient manner.
Advisors/Committee Members: Boucher,Christina A (committee chair), Sahni,Sartaj Kumar (committee member), Nelson,Corwin D (committee member).
Subjects/Keywords: coloredgraphs – graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Alipanahi Ramandi, B. (2020). Variants and Applications of Colored De Bruijn Graphs. (Doctoral Dissertation). University of Florida. Retrieved from https://ufdc.ufl.edu/UFE0056439
Chicago Manual of Style (16th Edition):
Alipanahi Ramandi, Bahareh. “Variants and Applications of Colored De Bruijn Graphs.” 2020. Doctoral Dissertation, University of Florida. Accessed January 19, 2021.
https://ufdc.ufl.edu/UFE0056439.
MLA Handbook (7th Edition):
Alipanahi Ramandi, Bahareh. “Variants and Applications of Colored De Bruijn Graphs.” 2020. Web. 19 Jan 2021.
Vancouver:
Alipanahi Ramandi B. Variants and Applications of Colored De Bruijn Graphs. [Internet] [Doctoral dissertation]. University of Florida; 2020. [cited 2021 Jan 19].
Available from: https://ufdc.ufl.edu/UFE0056439.
Council of Science Editors:
Alipanahi Ramandi B. Variants and Applications of Colored De Bruijn Graphs. [Doctoral Dissertation]. University of Florida; 2020. Available from: https://ufdc.ufl.edu/UFE0056439
Rutgers University
25.
Baron, Jacob D., 1988-.
Two problems on cycles in random graphs.
Degree: PhD, Mathematics, 2016, Rutgers University
URL: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/
► We prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of…
(more)
▼ We prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν3(G), of an edge-disjoint triangle packing is at most 2. Disproving a conjecture of R. Yuster [40], we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4. Second, write C(G) for the cycle space of a graph G, Cκ(G) for the subspace of C(G) spanned by the copies of Cκ in G, Tκ for the class of graphs satisfying Cκ(G) = C(G), and Qκ for the class of graphs each of whose edges lies in a Cκ. We prove that for every odd κ ≥ 3 and G = Gn,p, max p Pr(G ∈ Qκ Tκ) → 0; so the Cκ’s of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [12]. Third, we extend the seminal van den Berg–Kesten Inequality [9] on disjoint occurrence of two events to a setting with arbitrarily many events, where the quantity of interest is the maximum number that occur disjointly. This provides a handy tool for bounding upper tail probabilities for event counts in a product probability space.
Advisors/Committee Members: Kahn, Jeff (chair), Komlos, Janos (internal member), Saks, Michael (internal member), Yuster, Raphael (outside member).
Subjects/Keywords: Random graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Baron, Jacob D., 1. (2016). Two problems on cycles in random graphs. (Doctoral Dissertation). Rutgers University. Retrieved from https://rucore.libraries.rutgers.edu/rutgers-lib/51229/
Chicago Manual of Style (16th Edition):
Baron, Jacob D., 1988-. “Two problems on cycles in random graphs.” 2016. Doctoral Dissertation, Rutgers University. Accessed January 19, 2021.
https://rucore.libraries.rutgers.edu/rutgers-lib/51229/.
MLA Handbook (7th Edition):
Baron, Jacob D., 1988-. “Two problems on cycles in random graphs.” 2016. Web. 19 Jan 2021.
Vancouver:
Baron, Jacob D. 1. Two problems on cycles in random graphs. [Internet] [Doctoral dissertation]. Rutgers University; 2016. [cited 2021 Jan 19].
Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/.
Council of Science Editors:
Baron, Jacob D. 1. Two problems on cycles in random graphs. [Doctoral Dissertation]. Rutgers University; 2016. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/
University of Oxford
26.
Saller, Sophia.
Local limit theorem in random graphs and graphs on non-constant surfaces.
Degree: PhD, 2020, University of Oxford
URL: http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516
;
https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535
► The thesis is split into two parts. In the first part we prove a local limit theorem for the number of appearances of the complete…
(more)
▼ The thesis is split into two parts. In the first part we prove a local limit theorem for the number of appearances of the complete graph on four vertices, K4, in the Erdös-Rényi Random graph G(n, p) for p in (0, 1) a fixed constant. The proof of this is based on bounding the characteristic function of the number of K4 in G(n, p) by using different conditioning arguments for different ranges of t. The second part treats classes of graphs embeddable in either an orientable surface of Euler genus at most g(n), denoted by G^(g(n)), or non-orientable surface of Euler genus at most g(n), denoted by H^(g(n)), for different non-constant functions g(n). We first find bounds on the sizes of these classes and prove that as long as g(n) = o(n/log3(n)), the classes G^(g(n)) and H^(g(n)) both have a growth constant equal to the planar graph growth constant. As long as g(n) = O(n/log(n)) it is further shown that the classes Gg(n) and H^(g(n)) are both small. We then go on to show which properties graphs in these graph classes commonly display, such as giving bounds on the number of edges, faces, pendant vertices, the maximum degree and the probability of connectedness.
Subjects/Keywords: Random graphs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Saller, S. (2020). Local limit theorem in random graphs and graphs on non-constant surfaces. (Doctoral Dissertation). University of Oxford. Retrieved from http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535
Chicago Manual of Style (16th Edition):
Saller, Sophia. “Local limit theorem in random graphs and graphs on non-constant surfaces.” 2020. Doctoral Dissertation, University of Oxford. Accessed January 19, 2021.
http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535.
MLA Handbook (7th Edition):
Saller, Sophia. “Local limit theorem in random graphs and graphs on non-constant surfaces.” 2020. Web. 19 Jan 2021.
Vancouver:
Saller S. Local limit theorem in random graphs and graphs on non-constant surfaces. [Internet] [Doctoral dissertation]. University of Oxford; 2020. [cited 2021 Jan 19].
Available from: http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535.
Council of Science Editors:
Saller S. Local limit theorem in random graphs and graphs on non-constant surfaces. [Doctoral Dissertation]. University of Oxford; 2020. Available from: http://ora.ox.ac.uk/objects/uuid:147400e3-0a9b-46d1-b0c9-9acba7b94516 ; https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.813535
Indian Institute of Science
27.
Francis, Mathew C.
Intersection Graphs Of Boxes And Cubes.
Degree: PhD, Faculty of Engineering, 2011, Indian Institute of Science
URL: http://etd.iisc.ac.in/handle/2005/1027
► A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such…
(more)
▼ A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such that for u,v V(G), (u,v) E(G) ƒ (u) ƒ (v) ≠ . Interval
graphs are thus the intersection
graphs of closed intervals on the real line and unit interval
graphs are the intersection
graphs of unit length intervals on the real line. An interval on the real line can be generalized to a “kbox” in Rk.A kbox B =(R1,R2,...,Rk), where each Riis a closed interval on the real line, is defined to be the Cartesian product R1x R2x…x Rk. If each Ri is a unit length interval, we call B a k-cube. Thus, 1-boxes are just closed intervals on the real line whereas 2-boxes are axis-parallel rectangles in the plane. We study the intersection
graphs of k-boxes and k-cubes. The parameter boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. Thus, interval
graphs are the
graphs with boxicity at most 1 and unit interval
graphs are the
graphs with cubicity at most 1. These parameters were introduced by F. S.Roberts in 1969.
In some sense, the boxicity of a graph is a measure of how different a graph is from an interval graph and in a similar way, the cubicity is a measure of how different the graph is from a unit interval graph. We prove several upper bounds on the boxicity and cubicity of general as well as special classes of
graphs in terms of various graph parameters such as the maximum degree, the number of vertices and the bandwidth.
The following are some of the main results presented.
1. We show that for any graph G with maximum degree Δ , box(G)≤ Δ 22 . This result implies that bounded degree
graphs have bounded boxicity no matter how large the graph might be.
2. It was shown in [18] that the boxicity of a graph on n vertices with maximum degree Δ is O(Δ ln n). But a similar bound does not hold for the average degree davof a graph. [18] gives
graphs in which the boxicity is exponentially larger than davln n. We show that
even though an O(davln n) upper bound for boxicity does not hold for all
graphs, for almost all
graphs, boxicity is O(davln n).
3. The ratio of the cubicity to boxicity of any graph shown in [15] when combined with the results on boxicity show that cub(G) is O(Δ ln 2 n) and O(2 ln n) for any graph G on n vertices and with maximum degree . By using a randomized construction, we prove the better upper bound cub(G) ≤ [4(Δ + 1) ln n.]
4. Two results relating the cubicity of a graph to its bandwidth b are presented. First, it is shown that cub(G) ≤ 12(Δ + 1)[ ln(2b)] + 1. Next, we derive the upper bound cub(G) ≤ b + 1. This bound is used to derive new upper bounds on the cubicity of special graph classes like circular arc
graphs, cocomparability
graphs and ATfree
graphs in relation to the maximum degree.
5. The upper bound for cubicity in terms of the bandwidth gives an upper bound of Δ + 1 for the…
Advisors/Committee Members: Chandran, L Sunil (advisor).
Subjects/Keywords: Computer Graphics; Boxicity (Graphs); Cubicity (Graphs); Interval Graphs; Halin Graphs; Planar Graphs; Intersection Graphs; Random Graphs; Computer Science
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Francis, M. C. (2011). Intersection Graphs Of Boxes And Cubes. (Doctoral Dissertation). Indian Institute of Science. Retrieved from http://etd.iisc.ac.in/handle/2005/1027
Chicago Manual of Style (16th Edition):
Francis, Mathew C. “Intersection Graphs Of Boxes And Cubes.” 2011. Doctoral Dissertation, Indian Institute of Science. Accessed January 19, 2021.
http://etd.iisc.ac.in/handle/2005/1027.
MLA Handbook (7th Edition):
Francis, Mathew C. “Intersection Graphs Of Boxes And Cubes.” 2011. Web. 19 Jan 2021.
Vancouver:
Francis MC. Intersection Graphs Of Boxes And Cubes. [Internet] [Doctoral dissertation]. Indian Institute of Science; 2011. [cited 2021 Jan 19].
Available from: http://etd.iisc.ac.in/handle/2005/1027.
Council of Science Editors:
Francis MC. Intersection Graphs Of Boxes And Cubes. [Doctoral Dissertation]. Indian Institute of Science; 2011. Available from: http://etd.iisc.ac.in/handle/2005/1027
Oregon State University
28.
Polit, Gabriela.
Self-identity and self-esteem of recent female Mexican migrants in an even start program.
Degree: MA, Applied Anthropology, 2003, Oregon State University
URL: http://hdl.handle.net/1957/28456
► The purpose of the study is to explore the life experiences, identities, and self-esteem of a group of Mexican women who attend Even Start, a…
(more)
▼ The purpose of the study is to explore the life experiences, identities, and self-esteem of a group of
Mexican women who attend
Even Start, a family literacy program. The study also focuses on the effect
that the program has on the women's self-identities. I chose qualitative research considering I was
interested in their phenomenological experience. In order to gather data I interviewed ten women,
conducted a focus group with the women who were not interviewed, and did participant observation while
the women were in class.
The Mexican women I interviewed came to this country hoping to improve their socioeconomic
status. Most of them had relatives in the US and the support that they gave them made it easier for them to
come and get established. As a result of being away from their people and their culture, they had a hard
time, particularly at the beginning. Their illegal status and the fact that they didn't speak English
complicated things
even more. In spite of the many difficulties they had to face, their experiences in
this country have allowed them to improve their socioeconomic situation and to achieve greater levels of
independence.
In regards to their self-esteem, most of my informants have positive self-images. The few that
have lower levels of self-esteem were often mistreated by caregivers and their families were dysfunctional
in some way.
Even though a few have lower levels of self-esteem, all my informants felt loved by their
parents and other family members. Because of this and because they were raised in social environments
that fostered interdependence, my informants have generally developed into responsible and reliable people
who work towards their goals. Their identities mirror their society and in particular their social network.
At the core of 'who they are' are traits of the identities of caregivers that through active choices (Blumstein 1991) they came to internalize.
Even Start plays a crucial role in their self-identities for two main reasons. First, in the program
the women are taught English which is the basic tool they need in order to communicate and move around
in this country. Second, the women are around people from their country. By feeling they belong to a
larger community, the women feel supported and find strategies to cope with their reality. At the same
time, being around other Mexicans strengthens their Hispanic identity.
The following are recommendations that could be used by
Even Start to enhance the women's
self-esteem. (1) Incorporate more one-on-one activities to enable students to learn at their own pace and to
help participants with special needs to work without feeling a sense of pressure. (2) Provide the women
with the opportunity to improve their literacy skills in Spanish and to strengthen their knowledge in basic
areas. (3) Include activities that would allow the participants to release stress and thus to improve their
ability to concentrate. (4) Provide the students with skills that will enable them to find jobs or get
promoted.
…
Advisors/Committee Members: Rosenberger, Nancy R. (advisor), Young, John (committee member).
Subjects/Keywords: Even Start programs
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Polit, G. (2003). Self-identity and self-esteem of recent female Mexican migrants in an even start program. (Masters Thesis). Oregon State University. Retrieved from http://hdl.handle.net/1957/28456
Chicago Manual of Style (16th Edition):
Polit, Gabriela. “Self-identity and self-esteem of recent female Mexican migrants in an even start program.” 2003. Masters Thesis, Oregon State University. Accessed January 19, 2021.
http://hdl.handle.net/1957/28456.
MLA Handbook (7th Edition):
Polit, Gabriela. “Self-identity and self-esteem of recent female Mexican migrants in an even start program.” 2003. Web. 19 Jan 2021.
Vancouver:
Polit G. Self-identity and self-esteem of recent female Mexican migrants in an even start program. [Internet] [Masters thesis]. Oregon State University; 2003. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/1957/28456.
Council of Science Editors:
Polit G. Self-identity and self-esteem of recent female Mexican migrants in an even start program. [Masters Thesis]. Oregon State University; 2003. Available from: http://hdl.handle.net/1957/28456
Anna University
29.
Sivaram M.
Odd and even point crossover based Tabu ga for data
fusion in Information retrieval;.
Degree: Odd and even point crossover based Tabu ga for data
fusion in Information retrieval, 2015, Anna University
URL: http://shodhganga.inflibnet.ac.in/handle/10603/38935
► The retrieval schemes arrange process and list the documents in the newlinecorpus against the user query The schemes differ from each other in any one…
(more)
▼ The retrieval schemes arrange process and list the
documents in the newlinecorpus against the user query The schemes
differ from each other in any one newlineof the above mentioned
mechanisms Hence the literature has been flooded newlinewith
various retrieval models and schemes The merits of the various
schemes newlinecan be merged together to enhance the overall
performance of the retrieval newlinesystems The merging process
again depends on the proper selection of newlineindividual schemes
participating in the merging The optimization searching
newlinetools are used for selection This work indents to use
Genetic Algorithm GA newlineas the tool and we plan to test the
impact of odd and even point crossover newlineOdd and Even point
cross over is mainly used as the exploration tool and the
newlineimpact is tested over data fusion in information retrieval
newlineThe fusion function retrieval schemes and their weights
leads to a newlinehuge combination Finding an optimal solution from
this huge combination is newlineentirely based on the exploration
We used odd and even point crossover as newlinean exploration tool
This exploration tool suffers a setback of convergence newlineThe
convergence rate can be improved by merging Tabu search a best
local newlineSearch with the genetic algorithm newline
newline
reference p152-161.
Advisors/Committee Members: Batri K.
Subjects/Keywords: Genetic algorithm; Odd and even poin
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
M, S. (2015). Odd and even point crossover based Tabu ga for data
fusion in Information retrieval;. (Thesis). Anna University. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/38935
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
M, Sivaram. “Odd and even point crossover based Tabu ga for data
fusion in Information retrieval;.” 2015. Thesis, Anna University. Accessed January 19, 2021.
http://shodhganga.inflibnet.ac.in/handle/10603/38935.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
M, Sivaram. “Odd and even point crossover based Tabu ga for data
fusion in Information retrieval;.” 2015. Web. 19 Jan 2021.
Vancouver:
M S. Odd and even point crossover based Tabu ga for data
fusion in Information retrieval;. [Internet] [Thesis]. Anna University; 2015. [cited 2021 Jan 19].
Available from: http://shodhganga.inflibnet.ac.in/handle/10603/38935.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
M S. Odd and even point crossover based Tabu ga for data
fusion in Information retrieval;. [Thesis]. Anna University; 2015. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/38935
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Waterloo
30.
Pivotto, Irene.
On Excluded Minors for Even Cut Matroids.
Degree: 2007, University of Waterloo
URL: http://hdl.handle.net/10012/2680
► In this thesis we will present two main theorems that can be used to study minor minimal non even cut matroids. Given any signed graph…
(more)
▼ In this thesis we will present two main theorems that can be used to study
minor minimal non even cut matroids.
Given any signed graph we can associate an even cut matroid. However, given
an even cut matroid, there are in general, several signed graphs which
represent that matroid. This is in contrast to, for instance graphic (or
cographic) matroids, where all graphs corresponding to a particular
graphic matroid are essentially equivalent. To tackle the multiple
non equivalent representations of even cut matroids we use the concept of
Stabilizer first introduced by Wittle. Namely, we show the following:
given a "substantial" signed graph, which represents a matroid N that is a
minor of a matroid M, then if the signed graph extends to a signed graph
which represents M then it does so uniquely. Thus the representations of the
small matroid determine the representations of the larger matroid containing
it. This allows us to consider each representation of an even cut matroid
essentially independently.
Consider a small even cut matroid N that is a minor of a matroid M that is
not an even cut matroid. We would like to prove that there exists a
matroid N' which contains N and is contained in M such that the size of N'
is small and such that N' is not an even cut matroid (this would imply in
particular that there are only finitely many minimally non even cut
matroids containing N). Clearly, none of the representations of N extends to
M. We will show that (under certain technical conditions) starting from a
fixed representation of N, there exists a matroid N' which contains N
and is contained in M such that the size of N' is small and such that the
representation of N does not extend to N'.
Subjects/Keywords: even cut matroid
Record Details
Similar Records
Cite
Share »
Record Details
Similar Records
Cite
« Share
❌
APA ·
Chicago ·
MLA ·
Vancouver ·
CSE |
Export
to Zotero / EndNote / Reference
Manager
APA (6th Edition):
Pivotto, I. (2007). On Excluded Minors for Even Cut Matroids. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/2680
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Chicago Manual of Style (16th Edition):
Pivotto, Irene. “On Excluded Minors for Even Cut Matroids.” 2007. Thesis, University of Waterloo. Accessed January 19, 2021.
http://hdl.handle.net/10012/2680.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Pivotto, Irene. “On Excluded Minors for Even Cut Matroids.” 2007. Web. 19 Jan 2021.
Vancouver:
Pivotto I. On Excluded Minors for Even Cut Matroids. [Internet] [Thesis]. University of Waterloo; 2007. [cited 2021 Jan 19].
Available from: http://hdl.handle.net/10012/2680.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Pivotto I. On Excluded Minors for Even Cut Matroids. [Thesis]. University of Waterloo; 2007. Available from: http://hdl.handle.net/10012/2680
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
◁ [1] [2] [3] [4] [5] … [398] ▶
. 
Open Access Theses and Dissertations
