You searched for subject:(Graph).
Showing records 1 – 30 of
4232 total matches.
◁ [1] [2] [3] [4] [5] … [142] ▶
Mississippi State University
1.
Zhang, Fangyan.
Large-scale graph visual analytics.
Degree: PhD, Computer Science and Engineering, 2017, Mississippi State University
URL: http://sun.library.msstate.edu/ETD-db/theses/available/etd-10232017-142140/ 
;
► Large-scale graph analysis and visualization is becoming a more challenging task, due to the increasing amount of graph data. This dissertation focuses on methods…
(more)
▼ Large-scale
graph analysis and visualization is becoming a more challenging task, due to the increasing amount of
graph data. This dissertation focuses on methods to ease the task of exploring large-scale graphs through
graph sampling and visualization.
Graph sampling aims to reduce the complexity of
graph drawing, while preserving properties of the original
graph, allowing analysis of the smaller sample which yields the characteristics similar to those of the original
graph.
Graph visualization is an effective and intuitive approach to observing structures within
graph data. For large-scale graphs,
graph sampling and visualization are straightforward strategies to gain insights into common issues that are often encountered.
This dissertation evaluates commonly used
graph sampling methods through a combined visual and statistical comparison of graphs sampled at various rates based on random graphs, small-world graphs, scale-free graphs, and real-world graphs. This benchmark study can be used as a guideline in choosing the appropriate method for a particular
graph sampling task. In addition, this thesis proposes three types of distributed sampling algorithms and develops a sampling package on Spark. Compared with traditional/non-distributed
graph sampling approaches, the scalable distributed sampling approaches are as reliable as the traditional/non-distributed
graph sampling techniques, and they bring much needed improvement to sampling efficiency, especially with regards to topology-based sampling. This benchmark study in traditional/non-distributed
graph sampling is also applicable to distributed
graph sampling as well.
A contribution to the area of
graph visualization is also made through the presentation of a scalable
graph visualization system-BGS (Big
Graph Surfer) that creates hierarchical structure from an original
graph and provides interactive navigation along the hierarchy by expanding or collapsing clusters when visualizing large-scale graphs. A distributed computing framework-Spark provides the backend for BGS on clustering and visualization. This architecture makes it capable of visualizing a
graph up to 1 billion nodes or edges in real-time. In addition, BGS provides a series of hierarchy and
graph exploration methods, such as hierarchy view, hierarchy navigation, hierarchy search,
graph view,
graph navigation,
graph search, and other useful interactions. These functionalities facilitate the exploration of very large-scale graphs. Evaluation of BGS is performed through application to several representative of large-scale
graph datasets and comparison with other existing
graph visualization tools in scalability, usability, and flexibility.
The dissertation concludes with a summarization of the contributions and their improvement on large-scale
graph analysis and visualization, and a discussion about possible future work on this research field.
Advisors/Committee Members: Song Zhang (chair), J. Edward Swan II (chair), Andy D. Perkins (committee member), Pak Chung Wong (committee member).
Subjects/Keywords: large-scale graph; graph sampling; graph property; graph visualization; graph clustering; graph hierarchy
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):
Zhang, F. (2017). Large-scale graph visual analytics. (Doctoral Dissertation). Mississippi State University. Retrieved from http://sun.library.msstate.edu/ETD-db/theses/available/etd-10232017-142140/ ;
Chicago Manual of Style (16th Edition):
Zhang, Fangyan. “Large-scale graph visual analytics.” 2017. Doctoral Dissertation, Mississippi State University. Accessed November 20, 2019.
http://sun.library.msstate.edu/ETD-db/theses/available/etd-10232017-142140/ ;.
MLA Handbook (7th Edition):
Zhang, Fangyan. “Large-scale graph visual analytics.” 2017. Web. 20 Nov 2019.
Vancouver:
Zhang F. Large-scale graph visual analytics. [Internet] [Doctoral dissertation]. Mississippi State University; 2017. [cited 2019 Nov 20].
Available from: http://sun.library.msstate.edu/ETD-db/theses/available/etd-10232017-142140/ ;.
Council of Science Editors:
Zhang F. Large-scale graph visual analytics. [Doctoral Dissertation]. Mississippi State University; 2017. Available from: http://sun.library.msstate.edu/ETD-db/theses/available/etd-10232017-142140/ ;
University of Waterloo
2.
Sullivan, Matthew.
Planar graphs without 3-cycles and with 4-cycles far apart are 3-choosable.
Degree: 2016, University of Waterloo
URL: http://hdl.handle.net/10012/10859
► A graph G is said to be L-colourable if for a given list assignment L = {L(v)|v ∈ V (G)} there is a proper colouring…
(more)
▼ A graph G is said to be L-colourable if for a given list assignment L = {L(v)|v ∈ V (G)} there is a proper colouring c of G such that c(v) ∈ L(v) for all v in V (G). If G is L-colourable for all L with |L(v)| ≥ k for all v in V (G), then G is said to be k-choosable.
This paper focuses on two different ways to prove list colouring results on planar graphs. The first method will be discharging, which will be used to fuse multiple results into one theorem. The second method will be restricting the lists of vertices on the boundary and applying induction, which will show that planar graphs without 3- cycles and 4-cycles distance 8 apart are 3-choosable.
Subjects/Keywords: Graph Theory; Graph Colouring
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):
Sullivan, M. (2016). Planar graphs without 3-cycles and with 4-cycles far apart are 3-choosable. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/10859
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):
Sullivan, Matthew. “Planar graphs without 3-cycles and with 4-cycles far apart are 3-choosable.” 2016. Thesis, University of Waterloo. Accessed November 20, 2019.
http://hdl.handle.net/10012/10859.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Sullivan, Matthew. “Planar graphs without 3-cycles and with 4-cycles far apart are 3-choosable.” 2016. Web. 20 Nov 2019.
Vancouver:
Sullivan M. Planar graphs without 3-cycles and with 4-cycles far apart are 3-choosable. [Internet] [Thesis]. University of Waterloo; 2016. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/10012/10859.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Sullivan M. Planar graphs without 3-cycles and with 4-cycles far apart are 3-choosable. [Thesis]. University of Waterloo; 2016. Available from: http://hdl.handle.net/10012/10859
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Johannesburg
3.
Desormeaux, Wyatt Jules.
Total domination in graphs and graph modifications.
Degree: PhD, 2012, University of Johannesburg
URL: http://hdl.handle.net/10210/6158
► In this thesis, our primary objective is to investigate the effects that various graph modifications have on the total domination number of a graph. In…
(more)
▼ In this thesis, our primary objective is to investigate the effects that various graph modifications have on the total domination number of a graph. In Chapter 1, we introduce basic graph theory concepts and preliminary definitions. In Chapters 2 and 3, we investigate the graph modification of edge removal. In Chapter 2, we characterize graphs for which the removal of any arbitrary edge increases the total domination number. We also begin the investigation of graphs for which the removal of any arbitrary edge has no effect on the total domination number. In Chapter 3, we continue this investigation and determine the minimum number of edges required for these graphs. The contents of Chapters 2 and 3 have been published in Discrete Applied Mathematics [15] and [16]. In Chapter 4, we investigate the graph modification of edge addition. In particular, we focus our attention on graphs for which adding an edge between any pair of nonadjacent vertices has no effect on the total domination number. We characterize these graphs, determine a sharp upper bound on their total domination number and determine which combinations of order and total domination number are attainable. 10 11 We also study claw-free graphs which have this property. The contents of this chapter were published in Discrete Mathematics [20]. In Chapter 5, we investigate the graph modification of vertex removal. We characterize graphs for which the removal of any vertex changes the total domination number and find sharp upper and lower bounds on the total domination number of these graphs. We also characterize graphs for which the removal of an arbitrary vertex has no effect on the total domination number and we further show that they have no forbidden subgraphs. The contents of this chapter were published in Discrete Applied Mathematics [14]. In Chapters 6 and 7, we investigate the graph modification of edge lifting. In Chapter 6, we show that there are no trees for which every possible edge lift decreases the domination number, and we characterize trees for which every possible edge lift increases the domination number. The contents of Chapter 6 were published in the journal Quaestiones Mathematicae [17]. In Chapter 7, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. We characterize trees for which every possible edge lift increases the total domination number. At the time of the writing of this thesis, the contents of Chapter 7 have been published online in the Journal of Combinatorial Optimization [18] and will appear in print in a future issue.
Subjects/Keywords: Graph theory; Domination (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):
Desormeaux, W. J. (2012). Total domination in graphs and graph modifications. (Doctoral Dissertation). University of Johannesburg. Retrieved from http://hdl.handle.net/10210/6158
Chicago Manual of Style (16th Edition):
Desormeaux, Wyatt Jules. “Total domination in graphs and graph modifications.” 2012. Doctoral Dissertation, University of Johannesburg. Accessed November 20, 2019.
http://hdl.handle.net/10210/6158.
MLA Handbook (7th Edition):
Desormeaux, Wyatt Jules. “Total domination in graphs and graph modifications.” 2012. Web. 20 Nov 2019.
Vancouver:
Desormeaux WJ. Total domination in graphs and graph modifications. [Internet] [Doctoral dissertation]. University of Johannesburg; 2012. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/10210/6158.
Council of Science Editors:
Desormeaux WJ. Total domination in graphs and graph modifications. [Doctoral Dissertation]. University of Johannesburg; 2012. Available from: http://hdl.handle.net/10210/6158
Vanderbilt University
4.
Solava, Ryan William.
On the fine structure of graphs avoiding certain complete bipartite minors.
Degree: PhD, Mathematics, 2019, Vanderbilt University
URL: http://etd.library.vanderbilt.edu/available/etd-08182019-190904/
;
► Avoiding complete bipartite graphs as minors, and in particular K2,t as a minor, has been used to give sufficient conditions for Hamiltonicity. For this reason…
(more)
▼ Avoiding complete bipartite graphs as minors, and in particular K
2,t as a minor, has been used to give sufficient conditions for Hamiltonicity. For this reason and others, the classes of K
2,t-minor-free graphs are of interest. Ding gave a rough description of the K
2,t-minor-free graphs that gives necessary conditions for a
graph to be K
2,t-minor-free. We refine this description and characterize the K
2,t-minor-free graphs in the 3- and 4-connected cases, giving necessary and sufficient conditions. We also give a program for characterizing the 3-connected K
2,5-minor-free graphs. As part of this program, we prove a result on fan expansions that is of independent interest.
Advisors/Committee Members: Mark Ellingham (chair), Akram Aldroubi (committee member), Paul Edelman (committee member), Michael Mihalik (committee member), Jerry Spinrad (committee member).
Subjects/Keywords: Graph theory; Graph minors
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):
Solava, R. W. (2019). On the fine structure of graphs avoiding certain complete bipartite minors. (Doctoral Dissertation). Vanderbilt University. Retrieved from http://etd.library.vanderbilt.edu/available/etd-08182019-190904/ ;
Chicago Manual of Style (16th Edition):
Solava, Ryan William. “On the fine structure of graphs avoiding certain complete bipartite minors.” 2019. Doctoral Dissertation, Vanderbilt University. Accessed November 20, 2019.
http://etd.library.vanderbilt.edu/available/etd-08182019-190904/ ;.
MLA Handbook (7th Edition):
Solava, Ryan William. “On the fine structure of graphs avoiding certain complete bipartite minors.” 2019. Web. 20 Nov 2019.
Vancouver:
Solava RW. On the fine structure of graphs avoiding certain complete bipartite minors. [Internet] [Doctoral dissertation]. Vanderbilt University; 2019. [cited 2019 Nov 20].
Available from: http://etd.library.vanderbilt.edu/available/etd-08182019-190904/ ;.
Council of Science Editors:
Solava RW. On the fine structure of graphs avoiding certain complete bipartite minors. [Doctoral Dissertation]. Vanderbilt University; 2019. Available from: http://etd.library.vanderbilt.edu/available/etd-08182019-190904/ ;
University of Victoria
5.
Wu, Jian.
Graph-XLL: a graph library for extra large graph analytics on a single machine.
Degree: Department of Computer Science, 2019, University of Victoria
URL: http://hdl.handle.net/1828/11067
► Graph libraries containing already-implemented algorithms are highly desired since users can conveniently use the algorithms off-the-shelf to achieve fast analyt- ics and prototyping, rather than…
(more)
▼ Graph libraries containing already-implemented algorithms are highly desired since users can conveniently use the algorithms off-the-shelf to achieve fast analyt- ics and prototyping, rather than implementing the algorithms with lower-level APIs. Besides the ease of use, the ability to efficiently process extra large graphs is also required by users. The popular existing
graph libraries include the igraph R library and the NetworkX Python library. Although these libraries provide many off-the-shelf algorithms for users, the in-memory
graph representation limits their scalability for computing on large graphs. Therefore, in this work, we develop
Graph-XLL: a
graph library implemented using the WebGraph framework in a vertex-centric manner, with much less memory requirement compared to igraph and NetworkX. Scalable analytics for extra large graphs (up to tens of millions of vertices and billions of edges) can be achieved on a single consumer grade machine within a reasonable amount of time. Such computation would cause out-of-memory error if using igraph or NetworkX.
Advisors/Committee Members: Thomo, Alex (supervisor), Srinivasan, Venkatesh (supervisor).
Subjects/Keywords: Graph Analytics; WebGraph; Graph Library
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):
Wu, J. (2019). Graph-XLL: a graph library for extra large graph analytics on a single machine. (Masters Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/11067
Chicago Manual of Style (16th Edition):
Wu, Jian. “Graph-XLL: a graph library for extra large graph analytics on a single machine.” 2019. Masters Thesis, University of Victoria. Accessed November 20, 2019.
http://hdl.handle.net/1828/11067.
MLA Handbook (7th Edition):
Wu, Jian. “Graph-XLL: a graph library for extra large graph analytics on a single machine.” 2019. Web. 20 Nov 2019.
Vancouver:
Wu J. Graph-XLL: a graph library for extra large graph analytics on a single machine. [Internet] [Masters thesis]. University of Victoria; 2019. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/1828/11067.
Council of Science Editors:
Wu J. Graph-XLL: a graph library for extra large graph analytics on a single machine. [Masters Thesis]. University of Victoria; 2019. Available from: http://hdl.handle.net/1828/11067
Princeton University
6.
Gauthier, Gregory Joseph.
The structure of graphs with no cycles of length 0 (mod 3)
.
Degree: PhD, 2017, Princeton University
URL: http://arks.princeton.edu/ark:/88435/dsp010r9676355
► We examine the structure of graphs that have no cycles of length 0 (mod 3). We show that, if G is a simple 2-connected graph…
(more)
▼ We examine the structure of graphs that have no cycles of length 0 (mod 3). We show that, if G is a simple 2-connected
graph with no cycles of length 0 (mod 3), then G has two adjacent degree two vertices or G has two nonadjacent degree two vertices with the same neighborhood. Using this result, it follows that if G is a simple
graph with no cycles of length 0 (mod 3), then for every induced subgraph H of G, the modularity of H, defined as the number of even independent sets minus the number of odd independent sets, is either −1, 0, or 1.
Advisors/Committee Members: Seymour, Paul D (advisor).
Subjects/Keywords: graph;
structural graph theory;
swamp
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):
Gauthier, G. J. (2017). The structure of graphs with no cycles of length 0 (mod 3)
. (Doctoral Dissertation). Princeton University. Retrieved from http://arks.princeton.edu/ark:/88435/dsp010r9676355
Chicago Manual of Style (16th Edition):
Gauthier, Gregory Joseph. “The structure of graphs with no cycles of length 0 (mod 3)
.” 2017. Doctoral Dissertation, Princeton University. Accessed November 20, 2019.
http://arks.princeton.edu/ark:/88435/dsp010r9676355.
MLA Handbook (7th Edition):
Gauthier, Gregory Joseph. “The structure of graphs with no cycles of length 0 (mod 3)
.” 2017. Web. 20 Nov 2019.
Vancouver:
Gauthier GJ. The structure of graphs with no cycles of length 0 (mod 3)
. [Internet] [Doctoral dissertation]. Princeton University; 2017. [cited 2019 Nov 20].
Available from: http://arks.princeton.edu/ark:/88435/dsp010r9676355.
Council of Science Editors:
Gauthier GJ. The structure of graphs with no cycles of length 0 (mod 3)
. [Doctoral Dissertation]. Princeton University; 2017. Available from: http://arks.princeton.edu/ark:/88435/dsp010r9676355
University of Georgia
7.
Muskovin, Jennifer Anne.
On (0,2)-graphs and semibiplanes.
Degree: MA, Mathematics, 2009, University of Georgia
URL: http://purl.galileo.usg.edu/uga_etd/muskovin_jennifer_a_200905_ma
► A semibiplane is a connected point-block incidence structure such that any two points are in either 0 or 2 common blocks and any two blocks…
(more)
▼ A semibiplane is a connected point-block incidence structure such that any two points are in either 0 or 2 common blocks and any two blocks have either 0 or 2 common neighbors. A (0,2)-
graph is a connected
graph such that any pair of vertices has either 0 or 2 common neighbors. The incidence
graph of a semibiplane is a bipartite (0,2)-
graph. In this paper we construct (0,2)-graphs from known graphs by taking Cartesian products, quotients and adding matchings and construct semibiplanes by taking quotients of finite projective planes.
Advisors/Committee Members: Lenny Chastkofsky.
Subjects/Keywords: (0; 2)-graph
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):
Muskovin, J. A. (2009). On (0,2)-graphs and semibiplanes. (Masters Thesis). University of Georgia. Retrieved from http://purl.galileo.usg.edu/uga_etd/muskovin_jennifer_a_200905_ma
Chicago Manual of Style (16th Edition):
Muskovin, Jennifer Anne. “On (0,2)-graphs and semibiplanes.” 2009. Masters Thesis, University of Georgia. Accessed November 20, 2019.
http://purl.galileo.usg.edu/uga_etd/muskovin_jennifer_a_200905_ma.
MLA Handbook (7th Edition):
Muskovin, Jennifer Anne. “On (0,2)-graphs and semibiplanes.” 2009. Web. 20 Nov 2019.
Vancouver:
Muskovin JA. On (0,2)-graphs and semibiplanes. [Internet] [Masters thesis]. University of Georgia; 2009. [cited 2019 Nov 20].
Available from: http://purl.galileo.usg.edu/uga_etd/muskovin_jennifer_a_200905_ma.
Council of Science Editors:
Muskovin JA. On (0,2)-graphs and semibiplanes. [Masters Thesis]. University of Georgia; 2009. Available from: http://purl.galileo.usg.edu/uga_etd/muskovin_jennifer_a_200905_ma
University of Georgia
8.
Venkatesh, Sumana.
Subgraph pattern matching for graph databases.
Degree: MS, Computer Science, 2014, University of Georgia
URL: http://purl.galileo.usg.edu/uga_etd/venkatesh_sumana_201412_ms
► With the rapid increase of data in social and biological networks, ranging from a few dozen terabytes to many petabytes, managing the data with traditional…
(more)
▼ With the rapid increase of data in social and biological networks, ranging from a few dozen terabytes to many petabytes, managing the data with traditional databases has become very difficult. New data storage platforms have arisen to overcome lag in performance and capability from conventional approaches, which are built on traditional database technologies.
Graph Databases have gained increased popularity when dealing with storage and processing of huge data with relationships. With the need to query these
graph databases, fast and efficient
graph pattern matching algorithms are required, to find exact and inexact matches. This thesis presents a new
graph database that allows user to easily construct queries and run against huge vertex and edge labeled data
graph. The database has a rich user interface, which is implemented using JavaFX and it uses fast pattern matching algorithms for subgraph isomorphism problem to get desired matches. It has an added functionality to perform pattern matching using regular expressions.
Advisors/Committee Members: John A. Miller.
Subjects/Keywords: Graph Database
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):
Venkatesh, S. (2014). Subgraph pattern matching for graph databases. (Masters Thesis). University of Georgia. Retrieved from http://purl.galileo.usg.edu/uga_etd/venkatesh_sumana_201412_ms
Chicago Manual of Style (16th Edition):
Venkatesh, Sumana. “Subgraph pattern matching for graph databases.” 2014. Masters Thesis, University of Georgia. Accessed November 20, 2019.
http://purl.galileo.usg.edu/uga_etd/venkatesh_sumana_201412_ms.
MLA Handbook (7th Edition):
Venkatesh, Sumana. “Subgraph pattern matching for graph databases.” 2014. Web. 20 Nov 2019.
Vancouver:
Venkatesh S. Subgraph pattern matching for graph databases. [Internet] [Masters thesis]. University of Georgia; 2014. [cited 2019 Nov 20].
Available from: http://purl.galileo.usg.edu/uga_etd/venkatesh_sumana_201412_ms.
Council of Science Editors:
Venkatesh S. Subgraph pattern matching for graph databases. [Masters Thesis]. University of Georgia; 2014. Available from: http://purl.galileo.usg.edu/uga_etd/venkatesh_sumana_201412_ms
9.
Souza, Renato Ferreira de.
Resolução de problemas via teoria de grafos.
Degree: Mestrado, Mestrado Profissional em Matemática em Rede Nacional, 2015, University of São Paulo
URL: http://www.teses.usp.br/teses/disponiveis/55/55136/tde-06072015-103319/
;
► O objetivo deste trabalho é introduzir a noção de grafos familiarizando os alunos com um conceito pouco estudado no ensino fundamental e médio. Para isso,…
(more)
▼ O objetivo deste trabalho é introduzir a noção de grafos familiarizando os alunos com um conceito pouco estudado no ensino fundamental e médio. Para isso, foram estudados algumas situações práticas e a resolução por meio de grafos. A apresentação da teoria de grafos é feita utilizando alguns dos problemas clássicos (Pontes de Königsberg e o Problema do caixeiro-viajante) que originaram a teoria tal como é conhecida nos dias de hoje.
The aim of this work is to introduce the notion of graphs familiarizing students with a little concept studied in elementary and middle schools. For this, some practical situations were studied and the resolution through graphs. The presentation of the theory of graphs is done using some of the classic problems (The Königsberg bridge problem and The travelling salesman problem) that originated the theory as it is known today.
Advisors/Committee Members: Soares, Sérgio Henrique Monari.
Subjects/Keywords: Grafos; Graph
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):
Souza, R. F. d. (2015). Resolução de problemas via teoria de grafos. (Masters Thesis). University of São Paulo. Retrieved from http://www.teses.usp.br/teses/disponiveis/55/55136/tde-06072015-103319/ ;
Chicago Manual of Style (16th Edition):
Souza, Renato Ferreira de. “Resolução de problemas via teoria de grafos.” 2015. Masters Thesis, University of São Paulo. Accessed November 20, 2019.
http://www.teses.usp.br/teses/disponiveis/55/55136/tde-06072015-103319/ ;.
MLA Handbook (7th Edition):
Souza, Renato Ferreira de. “Resolução de problemas via teoria de grafos.” 2015. Web. 20 Nov 2019.
Vancouver:
Souza RFd. Resolução de problemas via teoria de grafos. [Internet] [Masters thesis]. University of São Paulo; 2015. [cited 2019 Nov 20].
Available from: http://www.teses.usp.br/teses/disponiveis/55/55136/tde-06072015-103319/ ;.
Council of Science Editors:
Souza RFd. Resolução de problemas via teoria de grafos. [Masters Thesis]. University of São Paulo; 2015. Available from: http://www.teses.usp.br/teses/disponiveis/55/55136/tde-06072015-103319/ ;
Louisiana State University
10.
D'souza, Kimberly Sevin.
Excluding a Weakly 4-connected Minor.
Degree: PhD, Applied Mathematics, 2016, Louisiana State University
URL: etd-04042016-220803
;
https://digitalcommons.lsu.edu/gradschool_dissertations/1368
► A 3-connected graph G is called weakly 4-connected if min (|E(G1)|, |E(G2)|) ≤ 4 holds for all 3-separations (G1,G2) of G. A 3-connected graph G…
(more)
▼ A 3-connected graph G is called weakly 4-connected if min (|E(G1)|, |E(G2)|) ≤ 4 holds for all 3-separations (G1,G2) of G. A 3-connected graph G is called quasi 4-connected if min (|V(G1)|, |V(G2)|) ≤ 4. We first discuss how to decompose a 3-connected graph into quasi 4-connected components. We will establish a chain theorem which will allow us to easily generate the set of all quasi 4-connected graphs. Finally, we will apply these results to characterizing all graphs which do not contain the Pyramid as a minor, where the Pyramid is the weakly 4-connected graph obtained by performing a Δ Y transformation to the octahedron. This result can be used to show an interesting characterization of quasi 4-connected, outer-projective graphs.
Subjects/Keywords: graph theory; graph minors; graph decomposition; Pyramid graph
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):
D'souza, K. S. (2016). Excluding a Weakly 4-connected Minor. (Doctoral Dissertation). Louisiana State University. Retrieved from etd-04042016-220803 ; https://digitalcommons.lsu.edu/gradschool_dissertations/1368
Chicago Manual of Style (16th Edition):
D'souza, Kimberly Sevin. “Excluding a Weakly 4-connected Minor.” 2016. Doctoral Dissertation, Louisiana State University. Accessed November 20, 2019.
etd-04042016-220803 ; https://digitalcommons.lsu.edu/gradschool_dissertations/1368.
MLA Handbook (7th Edition):
D'souza, Kimberly Sevin. “Excluding a Weakly 4-connected Minor.” 2016. Web. 20 Nov 2019.
Vancouver:
D'souza KS. Excluding a Weakly 4-connected Minor. [Internet] [Doctoral dissertation]. Louisiana State University; 2016. [cited 2019 Nov 20].
Available from: etd-04042016-220803 ; https://digitalcommons.lsu.edu/gradschool_dissertations/1368.
Council of Science Editors:
D'souza KS. Excluding a Weakly 4-connected Minor. [Doctoral Dissertation]. Louisiana State University; 2016. Available from: etd-04042016-220803 ; https://digitalcommons.lsu.edu/gradschool_dissertations/1368
University of Victoria
11.
Gelling, Eric Neil.
On 1-factorizations of the complete graph and the relationship to round robin schedules.
Degree: Department of Mathematics and Statistics, 2016, University of Victoria
URL: http://hdl.handle.net/1828/7341
► The following new results concerning 1-factorizations of the complete graph are proved: (1) There are exactly 6 equivalence classes of 1-factorizations of the complete graph…
(more)
▼ The following new results concerning 1-factorizations of the complete
graph are proved: (1) There are exactly 6 equivalence classes of 1-factorizations of the complete
graph with 8 vertices. (2). There are exactly 396 equivalence classes of 1-factorizations of the complete
graph with 10 vertices. Representatives of each of the equivalence classes are presented. The size of the automorphism group of each equivalence class of 1-factorizations of the complete
graph with 2n vertices for n ≤ 5 is also found.
Several theorems and results related to 1-factorizations of the complete
graph are presented, and the relationship to round robin schedules is shown. An application problem demonstrates the importance of the choice of the equivalence class of round robin schedules in the solvability of the problem.
Advisors/Committee Members: Odeh, Robert E. (supervisor).
Subjects/Keywords: 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):
Gelling, E. N. (2016). On 1-factorizations of the complete graph and the relationship to round robin schedules. (Masters Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/7341
Chicago Manual of Style (16th Edition):
Gelling, Eric Neil. “On 1-factorizations of the complete graph and the relationship to round robin schedules.” 2016. Masters Thesis, University of Victoria. Accessed November 20, 2019.
http://hdl.handle.net/1828/7341.
MLA Handbook (7th Edition):
Gelling, Eric Neil. “On 1-factorizations of the complete graph and the relationship to round robin schedules.” 2016. Web. 20 Nov 2019.
Vancouver:
Gelling EN. On 1-factorizations of the complete graph and the relationship to round robin schedules. [Internet] [Masters thesis]. University of Victoria; 2016. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/1828/7341.
Council of Science Editors:
Gelling EN. On 1-factorizations of the complete graph and the relationship to round robin schedules. [Masters Thesis]. University of Victoria; 2016. Available from: http://hdl.handle.net/1828/7341
Texas A&M University
12.
Xia, Xiangzhou.
Efficient and Scalable Listing of Four-Vertex Subgraph.
Degree: MS, Computer Science, 2016, Texas A&M University
URL: http://hdl.handle.net/1969.1/174219
► Identifying four-vertex subgraphs has long been recognized as a fundamental technique in bioinformatics and social networks. However, listing these structures is a challenging task, especially…
(more)
▼ Identifying four-vertex subgraphs has long been recognized as a fundamental technique in bioinformatics and social networks. However, listing these structures is a challenging task, especially for graphs that do not fit in RAM. To address this problem, we build a set of algorithms, models, and implementations that can handle massive graphs on commodity hardware. Our technique achieves 4 – 5 orders of magnitude speedup compared to the best prior methods on graphs with billions of edges, with external-memory operation equally efficient.
Advisors/Committee Members: Loguinov, Dmitri (advisor), Bettati, Riccardo (committee member), Reddy, A. L. Narasimha (committee member).
Subjects/Keywords: graph; motif
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):
Xia, X. (2016). Efficient and Scalable Listing of Four-Vertex Subgraph. (Masters Thesis). Texas A&M University. Retrieved from http://hdl.handle.net/1969.1/174219
Chicago Manual of Style (16th Edition):
Xia, Xiangzhou. “Efficient and Scalable Listing of Four-Vertex Subgraph.” 2016. Masters Thesis, Texas A&M University. Accessed November 20, 2019.
http://hdl.handle.net/1969.1/174219.
MLA Handbook (7th Edition):
Xia, Xiangzhou. “Efficient and Scalable Listing of Four-Vertex Subgraph.” 2016. Web. 20 Nov 2019.
Vancouver:
Xia X. Efficient and Scalable Listing of Four-Vertex Subgraph. [Internet] [Masters thesis]. Texas A&M University; 2016. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/1969.1/174219.
Council of Science Editors:
Xia X. Efficient and Scalable Listing of Four-Vertex Subgraph. [Masters Thesis]. Texas A&M University; 2016. Available from: http://hdl.handle.net/1969.1/174219
Wake Forest University
13.
Barnett, Joel Andrew.
Generalizations and Variations on Graph Pebbling.
Degree: 2014, Wake Forest University
URL: http://hdl.handle.net/10339/39310
► Graph pebbling involves determining the minimum number of pebbles needed so that regardless of the initial arrangement of pebbles on a graph, a pebble can…
(more)
▼ Graph pebbling involves determining the minimum number of pebbles needed so that regardless of the initial arrangement of pebbles on a graph, a pebble can be moved to any vertex using specified ``pebbling moves.'' This minimum number of pebbles is the pebbling number of a graph. We begin by making a brief exploration into path pebbling, which uses a sequence of pebbling moves instead of a single pebbling move. Returning to normal pebbling moves, we note that graph pebbling can be generalized by looking at a target distribution of pebbles, rather than just reaching one vertex with one pebble. We examine a contrast between pebbling on a labeled graph (where the target distribution is fixed) and an unlabeled graph (where the target distribution may be represented in multiple ways). We also seek to extend Jonas Sjostrand's Cover Pebbling Theorem to make calculating some pebbling numbers easier.
Subjects/Keywords: graph pebbling
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):
Barnett, J. A. (2014). Generalizations and Variations on Graph Pebbling. (Thesis). Wake Forest University. Retrieved from http://hdl.handle.net/10339/39310
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):
Barnett, Joel Andrew. “Generalizations and Variations on Graph Pebbling.” 2014. Thesis, Wake Forest University. Accessed November 20, 2019.
http://hdl.handle.net/10339/39310.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Barnett, Joel Andrew. “Generalizations and Variations on Graph Pebbling.” 2014. Web. 20 Nov 2019.
Vancouver:
Barnett JA. Generalizations and Variations on Graph Pebbling. [Internet] [Thesis]. Wake Forest University; 2014. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/10339/39310.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Barnett JA. Generalizations and Variations on Graph Pebbling. [Thesis]. Wake Forest University; 2014. Available from: http://hdl.handle.net/10339/39310
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Johannesburg
14.
Immelman, Yolande.
On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph.
Degree: 2009, University of Johannesburg
URL: http://hdl.handle.net/10210/2359
► M.Sc.
In this dissertation we study two types of colourings, namely line-distinguishing colourings and harmonious colourings. A line-distinguishing colouring of a graph G is a…
(more)
▼ M.Sc.
In this dissertation we study two types of colourings, namely line-distinguishing colourings and harmonious colourings. A line-distinguishing colouring of a graph G is a k-colouring of the vertices of G such that no two edges have the same colour. The line-distinguishing chromatic number G is defined as the smallest k such that G has a line-distinguishing k-colouring. A harmonious colouring of a graph G is a proper k-colouring of the vertices of G such that no two edges have the same colour, i.e. no two adjacent vertices can have the same colour. The harmonious chromatic number hG is defined as the smallest k such that G has a line-distinguishing k-colouring. In Chapter 0 we discuss some of the terminology and definitions used later on in our study. In Chapter 1 we introduce line-distinguishing colourings and consider the line-distinguishing chromatic number of certain familiar classes of graphs such as trees, paths, cycles and complete graphs. We also consider graphs with line-distinguishing chromatic number G equal to the usual chromatic number G, and we compare G with the chromatic index G of a graph. In Chapter 2 we mostly discuss minimal line-distinguishing (MLD) colourings. We consider minimal line-distinguishing colourings and graphs of diameter two as well as classes of regular MLD-colourable graphs. We also introduce the concept of distance regular graphs and discuss minimal line-distinguishing colourings in these graphs. In Chapter 3 we introduce a new parameter, namely the upper line-distinguishing chromatic number H G of a graph. We investigate H G for paths and cycles, and consider graphs with small upper line-distinguishing chromatic numbers. In Chapter 4 we consider the second type of colouring studied in this dissertation, namely harmonious colourings. We define the harmonious chromatic number hG and determine hG for certain classes of graphs such as paths, trees, cycles and complete graphs. In Chapter 5 we discuss upper and lower bound for hG. In Chapter 6 we discuss the upper harmonious chromatic number HG of a graph, and we determine HG for paths and cycles. We also consider graphs satisfying HG G 1. The purpose of this study is to compile a resource which will give a thorough and well-integrated background on line-distinguishing and harmonious colourings. It is also intended to lay the groundwork for further doctoral studies in the field of colourings.
Subjects/Keywords: Graph 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):
Immelman, Y. (2009). On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph. (Thesis). University of Johannesburg. Retrieved from http://hdl.handle.net/10210/2359
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):
Immelman, Yolande. “On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph.” 2009. Thesis, University of Johannesburg. Accessed November 20, 2019.
http://hdl.handle.net/10210/2359.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Immelman, Yolande. “On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph.” 2009. Web. 20 Nov 2019.
Vancouver:
Immelman Y. On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph. [Internet] [Thesis]. University of Johannesburg; 2009. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/10210/2359.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Immelman Y. On the (upper) line-distinguishing and (upper) harmonious chromatic numbers of a graph. [Thesis]. University of Johannesburg; 2009. Available from: http://hdl.handle.net/10210/2359
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Rochester Institute of Technology
15.
Culak, Juraj.
Separators in High-Genus Near-Planar Graphs.
Degree: MS, Computer Science (GCCIS), 2016, Rochester Institute of Technology
URL: https://scholarworks.rit.edu/theses/9427
► Graph separators are a powerful tool that are motivated by divide and conquer algorithms on graphs. Results have shown the existence of separators in…
(more)
▼ Graph separators are a powerful tool that are motivated by divide and conquer algorithms on graphs. Results have shown the existence of separators in arbitrary planar graphs and other graphs with less restricted structure. This work explores planar separators and the planar separator theorem, as well as the existence of separators in the class of high genus near-planar graphs. These graphs have unbounded genus, where additionally the edges that cross each other are located near each other in the
graph. Several different
graph classes that are high genus near-planar graphs are investigated for their feasibility for an extended separator theorem result.
Advisors/Committee Members: Ivona Bezakova, Edith Hemaspaandra, Stanisław Radziszowski.
Subjects/Keywords: Graph separators
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):
Culak, J. (2016). Separators in High-Genus Near-Planar Graphs. (Masters Thesis). Rochester Institute of Technology. Retrieved from https://scholarworks.rit.edu/theses/9427
Chicago Manual of Style (16th Edition):
Culak, Juraj. “Separators in High-Genus Near-Planar Graphs.” 2016. Masters Thesis, Rochester Institute of Technology. Accessed November 20, 2019.
https://scholarworks.rit.edu/theses/9427.
MLA Handbook (7th Edition):
Culak, Juraj. “Separators in High-Genus Near-Planar Graphs.” 2016. Web. 20 Nov 2019.
Vancouver:
Culak J. Separators in High-Genus Near-Planar Graphs. [Internet] [Masters thesis]. Rochester Institute of Technology; 2016. [cited 2019 Nov 20].
Available from: https://scholarworks.rit.edu/theses/9427.
Council of Science Editors:
Culak J. Separators in High-Genus Near-Planar Graphs. [Masters Thesis]. Rochester Institute of Technology; 2016. Available from: https://scholarworks.rit.edu/theses/9427
University of New South Wales
16.
Shang, Haichuan.
Efficient algorithms for graph substructure search.
Degree: Computer Science & Engineering, 2011, University of New South Wales
URL: http://handle.unsw.edu.au/1959.4/51214
;
https://unsworks.unsw.edu.au/fapi/datastream/unsworks:9931/SOURCE02?view=true
► Many recent applications strongly demand efficient and effective management of graph structured data such as paths, trees, and general graphs. These applications include Bioinformatics, Chemistry,…
(more)
▼ Many recent applications strongly demand efficient and effective management of
graph structured data such as paths, trees, and general graphs. These applications include Bioinformatics, Chemistry, Social networks, Software and Data Engineering, World Wide Web, etc.The goal of this thesis is to investigate
graph substructure search problem. Its focus is placed on enhancing efficiency in subgraph containment search and similarity search. Three subproblems are studied: (1) subgraph containment query; (2) substructure similaritysearch; and (3) similarity search on supergraph containment.For the subgraph containment query problem, efficient techniques are developed to retrieve graphs, containing a given query
graph, from a large set of graphs. Most of the existing techniques based on the framework of filtering-and-verification to reduce the precise computation costs. While the existing techniques worked well for small query graphs, the verification phase became a bottleneck when the query
graph size increased. Motivated by this, a novel and efficient algorithm is firstly proposed in this thesis for testing subgraph isomorphism. Secondly, a new feature-based index technique is developed to accommodate the above algorithm in the filtering phase.Substructure similarity search is to retrieve graphs that approximately contain a given query
graph. It has many applications, e.g., detecting similar functions among chemical compounds. This thesis proposes a novel indexing technique, GrafD-Index, to index graphs according to their “distances” to features. Then lower and upper bounding techniques are developed to exploit the GrafD-Index to (1) prune non-promising graphs and (2) include graphs whose similarities are guaranteed to exceed the given similarity threshold. Considering that the verification phase is not well studied and plays the dominant role in the whole process, efficient algorithms are devised to verify candidates.This thesis also investigates the problem of efficiently retrieving all data graphs approximately contained by a query
graph, namely similarity search on supergraph containment. A novel and efficient index is proposed to boost the efficiency of query processing. The index supports two construction strategies which aim at optimizing the performance for data distributions. Moreover, an algorithm is developed by effectively merging the indexes of individual data graphs; this not only reduces the index size but also further reduces the query processing time.
Advisors/Committee Members: Lin, Xuemin, Computer Science & Engineering, Faculty of Engineering, UNSW.
Subjects/Keywords: Graph database
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):
Shang, H. (2011). Efficient algorithms for graph substructure search. (Doctoral Dissertation). University of New South Wales. Retrieved from http://handle.unsw.edu.au/1959.4/51214 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:9931/SOURCE02?view=true
Chicago Manual of Style (16th Edition):
Shang, Haichuan. “Efficient algorithms for graph substructure search.” 2011. Doctoral Dissertation, University of New South Wales. Accessed November 20, 2019.
http://handle.unsw.edu.au/1959.4/51214 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:9931/SOURCE02?view=true.
MLA Handbook (7th Edition):
Shang, Haichuan. “Efficient algorithms for graph substructure search.” 2011. Web. 20 Nov 2019.
Vancouver:
Shang H. Efficient algorithms for graph substructure search. [Internet] [Doctoral dissertation]. University of New South Wales; 2011. [cited 2019 Nov 20].
Available from: http://handle.unsw.edu.au/1959.4/51214 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:9931/SOURCE02?view=true.
Council of Science Editors:
Shang H. Efficient algorithms for graph substructure search. [Doctoral Dissertation]. University of New South Wales; 2011. Available from: http://handle.unsw.edu.au/1959.4/51214 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:9931/SOURCE02?view=true
University of Newcastle
17.
Wijaya, Rachel Wulan Nirmalasari.
Advances in graph labelings.
Degree: MPhil, 2018, University of Newcastle
URL: http://hdl.handle.net/1959.13/1384118
► Masters Research - Master of Philosophy (MPhil)
A graph labeling is a mapping that assigns natural numbers to vertices and/or edges of a graph. In…
(more)
▼ Masters Research - Master of Philosophy (MPhil)
A graph labeling is a mapping that assigns natural numbers to vertices and/or edges of a graph. In this thesis, we consider two types of labeling; magic and irregular labeling. In both labelings, we label both vertices and edges of the graph. This type of labeling is called total labeling. In irregular labeling we can repeat some numbers in the graph, but the weights of every graph element are pairwise distinct. A graph is called <i>H</i>-supermagic if the weight of every subgraph <i>H</i> of the graph is constant. In magic labeling, we prove that banana tree, firecracker, flower and grid graph are <i>H</i>-supermagic. Banana tree graph is an amalgamation of connected graphs. Therefore result for banana trees is an immediate consequence of a theorem about amalgamations of connected graphs from Maryati et al. The result for firecracker graph is obtained by a similar method. For flower graph, we provide results for odd order. In the grid graphs, we prove that it is <i>H</i>-supermagic by induction. In irregular labeling, we consider the weight of the corresponding edges. If the weight of every edge is different we called the labeling edge irregular total labeling. We prove that the grid graphs are edge irregular.
Advisors/Committee Members: University of Newcastle. Faculty of Science, School of Mathematical and Physical Sciences.
Subjects/Keywords: graph labelings
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):
Wijaya, R. W. N. (2018). Advances in graph labelings. (Masters Thesis). University of Newcastle. Retrieved from http://hdl.handle.net/1959.13/1384118
Chicago Manual of Style (16th Edition):
Wijaya, Rachel Wulan Nirmalasari. “Advances in graph labelings.” 2018. Masters Thesis, University of Newcastle. Accessed November 20, 2019.
http://hdl.handle.net/1959.13/1384118.
MLA Handbook (7th Edition):
Wijaya, Rachel Wulan Nirmalasari. “Advances in graph labelings.” 2018. Web. 20 Nov 2019.
Vancouver:
Wijaya RWN. Advances in graph labelings. [Internet] [Masters thesis]. University of Newcastle; 2018. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/1959.13/1384118.
Council of Science Editors:
Wijaya RWN. Advances in graph labelings. [Masters Thesis]. University of Newcastle; 2018. Available from: http://hdl.handle.net/1959.13/1384118
Princeton University
18.
Sandon, Colin Peter.
Community Detection in the Stochastic Block Model: fundamental limits
.
Degree: PhD, 2017, Princeton University
URL: http://arks.princeton.edu/ark:/88435/dsp011v53k058n
► In recent years, there have been many developments in the study of the stochastic block model, starting with a paper by Decelle et al. in…
(more)
▼ In recent years, there have been many developments in the study of the stochastic block model, starting with a paper by Decelle et al. in which they conjecture that in the sparse stochastic block model, efficient community detection is possible if and only if the parameters are above the Kesten-Stigum bound. Massouli\'e , Mossel et al., and Bordenave et al. succeeded in proving the positive half of this conjecture in the 2-community symmetric case. Also, Mossel et al. proved that community detection is impossible below the KS bound in the 2-community symmetric case. On another note, Abbe et al. and Mossel et al. found a threshold for when it was possible to completely recover the communities in the 2-community symmetric case.
In this thesis, we go beyond the 2-community symmetric case to prove the positive half of the conjecture for the general SBM. In order to do that, we construct a linearized belief propagation algorithm that runs in O(nlog n) time and prove that it detects communities whenever the parameters of the SBM are above the KS bound. We also prove that unlike in the 2-community symmetric case, in the general SBM there are choices of parameters below the KS threshold for which one can detect communities in exponential time, confirming another conjecture by Decelle et al. This result implies that we cannot prove the impossibility of efficient community detection below the KS bound without proving some major conjectures on what compuations can be done efficiently. We also extend the threshold for when it is possible to completely recover the communities to the general SBM.
Advisors/Committee Members: Abbe, Emmanuel A (advisor).
Subjects/Keywords: clustering;
graph
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):
Sandon, C. P. (2017). Community Detection in the Stochastic Block Model: fundamental limits
. (Doctoral Dissertation). Princeton University. Retrieved from http://arks.princeton.edu/ark:/88435/dsp011v53k058n
Chicago Manual of Style (16th Edition):
Sandon, Colin Peter. “Community Detection in the Stochastic Block Model: fundamental limits
.” 2017. Doctoral Dissertation, Princeton University. Accessed November 20, 2019.
http://arks.princeton.edu/ark:/88435/dsp011v53k058n.
MLA Handbook (7th Edition):
Sandon, Colin Peter. “Community Detection in the Stochastic Block Model: fundamental limits
.” 2017. Web. 20 Nov 2019.
Vancouver:
Sandon CP. Community Detection in the Stochastic Block Model: fundamental limits
. [Internet] [Doctoral dissertation]. Princeton University; 2017. [cited 2019 Nov 20].
Available from: http://arks.princeton.edu/ark:/88435/dsp011v53k058n.
Council of Science Editors:
Sandon CP. Community Detection in the Stochastic Block Model: fundamental limits
. [Doctoral Dissertation]. Princeton University; 2017. Available from: http://arks.princeton.edu/ark:/88435/dsp011v53k058n
University of Waterloo
19.
Arroyo Guevara, Alan Marcelo.
On Geometric Drawings of Graphs.
Degree: 2018, University of Waterloo
URL: http://hdl.handle.net/10012/13103
► This thesis is about geometric drawings of graphs and their topological generalizations. First, we study pseudolinear drawings of graphs in the plane. A pseudolinear drawing…
(more)
▼ This thesis is about geometric drawings of graphs and their topological generalizations.
First, we study pseudolinear drawings of graphs in the plane. A pseudolinear drawing is one in which every edge can be extended into an infinite simple arc in the plane, homeomorphic to ℝ, and such that every two extending arcs cross exactly once. This is a natural generalization of the well-studied class of rectilinear drawings, where edges are straight-line segments. Although, the problem of deciding whether a drawing is homeomorphic to a rectilinear drawing is NP-hard, in this work we characterize the minimal forbidden subdrawings for pseudolinear drawings and we also provide a polynomial-time algorithm for recognizing this family of drawings.
Second, we consider the problem of transforming a topological drawing into a similar rectilinear drawing preserving the set of crossing pairs of edges. We show that, under some circumstances, pseudolinearity is a necessary and sufficient condition for the existence of such transformation. For this, we prove a generalization of Tutte's Spring Theorem for drawings with crossings placed
in a particular way.
Lastly, we study drawings of Kn in the sphere whose edges can be extended to an arrangement of pseudocircles. An arrangement of pseudocircles is a set of simple closed curves in the sphere such that every two intersect at most twice. We show that (i) there is drawing of K10 that cannot be extended into an arrangement of pseudocircles; and (ii) there is a drawing of K9 that can be extended to an arrangement of pseudocircles, but no extension satisfies that every two pseudocircles intersects exactly twice. We also introduce the notion pseudospherical drawings of Kn, a generalization of spherical drawings in which each edge is a minor arc of a great circle. We show that these drawings are characterized by a simple local property. We also show that every pseudospherical drawing has an extension into an arrangement of pseudocircles where the ``at most twice'' condition is replaced by ``exactly twice''.
Subjects/Keywords: combinatorics; crossing numbers; graph theory; graph; drawing; complete graph; rectilinear; graph embedding; graph drawing
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):
Arroyo Guevara, A. M. (2018). On Geometric Drawings of Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/13103
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):
Arroyo Guevara, Alan Marcelo. “On Geometric Drawings of Graphs.” 2018. Thesis, University of Waterloo. Accessed November 20, 2019.
http://hdl.handle.net/10012/13103.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Arroyo Guevara, Alan Marcelo. “On Geometric Drawings of Graphs.” 2018. Web. 20 Nov 2019.
Vancouver:
Arroyo Guevara AM. On Geometric Drawings of Graphs. [Internet] [Thesis]. University of Waterloo; 2018. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/10012/13103.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Arroyo Guevara AM. On Geometric Drawings of Graphs. [Thesis]. University of Waterloo; 2018. Available from: http://hdl.handle.net/10012/13103
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Western Michigan University
20.
Alhulwah, Khawlah Hamad.
Structures of Derived Graphs.
Degree: PhD, Mathematics, 2017, Western Michigan University
URL: https://scholarworks.wmich.edu/dissertations/3204
► One of the most familiar derived graphs are line graphs. The line graph L(G) of a graph G is the graph whose vertices are…
(more)
▼ One of the most familiar derived graphs are line graphs. The line
graph L(G) of a
graph G is the
graph whose vertices are the edges of
G where two vertices of
L(G) are adjacent if and only if the corresponding edges of
G are adjacent. One of the best- known results on the structure of line graphs deals with forbidden subgraphs by Beineke. A characterization of graphs whose line
graph is Hamiltonian is due to Harary and Nash-Williams. Iterated line graphs of almost all connected graphs were shown to be Hamiltonian by Chartrand. The girth of a
graph G is the length of a smallest cycle of
G. An
r-regular
graph of girth
g of minimum order is called a cage. Another class of derived graphs having a connection with cages was introduced by Schwenk. For a
graph G having girth 2
k + 1, the Schwenk
graph G* of
G has the set of all (
k + 1)-paths as its vertex set where two vertices
P and
Q are adjacent in
G* if and only if
P and
Q have only an end-vertex in common and the vertices of
P and
Q induce a (2
k + 1)-cycle. In this work, we introduce two new classes of derived graphs, called ℓ -line graphs and
Z-graphs. The concept of ℓ -line graphs is a generalization of line graphs and Schwenk graphs, while the
Z-graphs provide a different view of certain line graphs. We primarily study the structures of these derived graphs. Results, conjectures and problems on the structural properties such that connectedness, decompositions, Hamiltonicity and planarity of these graphs are presented.
Advisors/Committee Members: Dr. Ping Zhang, Dr. Gary Chartrand, Dr. Allen Schwenk.
Subjects/Keywords: Line graph; Peterson graph; complete graph; graph; derived graphs; 3-line graph; Applied Mathematics
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):
Alhulwah, K. H. (2017). Structures of Derived Graphs. (Doctoral Dissertation). Western Michigan University. Retrieved from https://scholarworks.wmich.edu/dissertations/3204
Chicago Manual of Style (16th Edition):
Alhulwah, Khawlah Hamad. “Structures of Derived Graphs.” 2017. Doctoral Dissertation, Western Michigan University. Accessed November 20, 2019.
https://scholarworks.wmich.edu/dissertations/3204.
MLA Handbook (7th Edition):
Alhulwah, Khawlah Hamad. “Structures of Derived Graphs.” 2017. Web. 20 Nov 2019.
Vancouver:
Alhulwah KH. Structures of Derived Graphs. [Internet] [Doctoral dissertation]. Western Michigan University; 2017. [cited 2019 Nov 20].
Available from: https://scholarworks.wmich.edu/dissertations/3204.
Council of Science Editors:
Alhulwah KH. Structures of Derived Graphs. [Doctoral Dissertation]. Western Michigan University; 2017. Available from: https://scholarworks.wmich.edu/dissertations/3204
Louisiana State University
21.
Fallon, Joshua E.
Two Results in Drawing Graphs on Surfaces.
Degree: PhD, Discrete Mathematics and Combinatorics, 2018, Louisiana State University
URL: https://digitalcommons.lsu.edu/gradschool_dissertations/4611
► In this work we present results on crossing-critical graphs drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We…
(more)
▼ In this work we present results on crossing-critical graphs drawn on non-planar surfaces and results on edge-hamiltonicity of graphs on the Klein bottle. We first give an infinite family of graphs that are 2-crossing-critical on the projective plane. Using this result, we construct 2-crossing-critical graphs for each non-orientable surface. Next, we use 2-amalgamations to construct 2-crossing-critical graphs for each orientable surface other than the sphere. Finally, we contribute to the pursuit of characterizing 4-connected graphs that embed on the Klein bottle and fail to be edge-hamiltonian. We show that known 4-connected counterexamples to edge-hamiltonicity on the Klein bottle are hamiltonian and their structure allows restoration of edge-hamiltonicity with only a small change.
Subjects/Keywords: graph theory; combinatorics; topological 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):
Fallon, J. E. (2018). Two Results in Drawing Graphs on Surfaces. (Doctoral Dissertation). Louisiana State University. Retrieved from https://digitalcommons.lsu.edu/gradschool_dissertations/4611
Chicago Manual of Style (16th Edition):
Fallon, Joshua E. “Two Results in Drawing Graphs on Surfaces.” 2018. Doctoral Dissertation, Louisiana State University. Accessed November 20, 2019.
https://digitalcommons.lsu.edu/gradschool_dissertations/4611.
MLA Handbook (7th Edition):
Fallon, Joshua E. “Two Results in Drawing Graphs on Surfaces.” 2018. Web. 20 Nov 2019.
Vancouver:
Fallon JE. Two Results in Drawing Graphs on Surfaces. [Internet] [Doctoral dissertation]. Louisiana State University; 2018. [cited 2019 Nov 20].
Available from: https://digitalcommons.lsu.edu/gradschool_dissertations/4611.
Council of Science Editors:
Fallon JE. Two Results in Drawing Graphs on Surfaces. [Doctoral Dissertation]. Louisiana State University; 2018. Available from: https://digitalcommons.lsu.edu/gradschool_dissertations/4611
Penn State University
22.
Viswanath, Archana.
Enhanced force directed graph embedding algorithms.
Degree: MS, Computer Science and Engineering, 2008, Penn State University
URL: https://etda.libraries.psu.edu/catalog/8793
► Graph embedding is a pictorial representation of a graph G(V;E) on a surface, where V is the set of vertices and E is the set…
(more)
▼ Graph embedding is a pictorial representation of a
graph G(V;E) on a surface, where V is the set of vertices and E is
the set of edges of G. Its primary purpose is to draw the vertices
V and edges E of graph G in an aesthetically pleasing manner.
Several graph embedding algorithms exist in literature with force
based algorithms [1] forming one such category. Force based
algorithms [1] represent the vertices and edges of a graph as a
physical system of steel rings and springs respectively. They
obtain the nal graph layout through an iterative process of energy
minimization of the physical system. A good choice of embedding can
lead to particularly illuminating diagrams revealing several
underlying details about the problem on hand. Fruchterman Reingold
force directed algorithm [1] is an example of a force based
algorithm. In this thesis we consider the Fruchterman Reingold
force directed algorithm [1] as a prototype of force based
algorithms and compare our improvisations with respect to it. The
Fruchterman Reingold force directed algorithm [1] has a limitation
of generating good quality graph layouts only after several
iterations of running. In this thesis, we propose a weight based
technique to not only handle this problem but also improve the
graph quality. We add uniform weights to all edges of the graph and
analyze its eect on the quality and runtime of the graph layouts.
This additional edge weight magnies the eect of the attractive
force between a vertex and its neighbor. This brings the vertices
close together, in lesser time compared to the Fruchterman Reingold
algorithm [1]. Scaling the attractive force helps obtain shorter
edges between neighboring vertices. The shorter an edge, the lesser
the available length to intersect with other edges. This thesis
also addresses the incorporation of user dened initial placement of
vertices in the Fruchterman Reingold algorithm [1]. This may be
particularly useful when the user may be aware of the positions of
certain vertices in the graph. Hence, a non standard initial layout
might help generate a better layout in lesser time. The weight
enhanced Fruchterman Reingold force directed algorithm [1] improves
the quality of graph layouts on an average by 89.86% and decreases
the number of iterations of the Fruchterman Reingold algorithm by
80%. We apply our weight enhanced Fruchterman-Reingold algorithm as
a pre-proc-essing step to clustering done with Kmeans [2] for
classifying documents. Compared to Kmeans [2], our weight enhanced
Fruchterman Reingold algorithm reduced the document misclassication
rate on an average by 40.4% while improving the internal cluster
quality (intra-cluster cohesiveness and inter-cluster similarity)
on an average by 55.5%.
Subjects/Keywords: graph embedding; graph drawing; force directed
method
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):
Viswanath, A. (2008). Enhanced force directed graph embedding algorithms. (Masters Thesis). Penn State University. Retrieved from https://etda.libraries.psu.edu/catalog/8793
Chicago Manual of Style (16th Edition):
Viswanath, Archana. “Enhanced force directed graph embedding algorithms.” 2008. Masters Thesis, Penn State University. Accessed November 20, 2019.
https://etda.libraries.psu.edu/catalog/8793.
MLA Handbook (7th Edition):
Viswanath, Archana. “Enhanced force directed graph embedding algorithms.” 2008. Web. 20 Nov 2019.
Vancouver:
Viswanath A. Enhanced force directed graph embedding algorithms. [Internet] [Masters thesis]. Penn State University; 2008. [cited 2019 Nov 20].
Available from: https://etda.libraries.psu.edu/catalog/8793.
Council of Science Editors:
Viswanath A. Enhanced force directed graph embedding algorithms. [Masters Thesis]. Penn State University; 2008. Available from: https://etda.libraries.psu.edu/catalog/8793
Ryerson University
23.
Patel, Sonal.
Clique Listing Algorithms and Characteristics of Cliques in Random Graphics.
Degree: 2010, Ryerson University
URL: https://digital.library.ryerson.ca/islandora/object/RULA%3A1845
► In this thesis we address three main problems in clique detection in the area of Graph Theory. i) Most of current methods for clique detection…
(more)
▼ In this thesis we address three main problems in clique detection in the area of
Graph Theory. i) Most of current methods for clique detection are time consuming (can take exponential time to the size of input
graph), so there is a practical limit on size of input
graph. In this thesis we propose three different methods for estimating the number of cliques. We examine these methods for various graphs and conclude that they efficiently find the number of cliques within 5% error typically. ii) We compare various versions of the Bron-Kerbosch (BK) clique listing algorithm to discover a method of combining the best features of different versions. We test our new versions of BK for various inputs. iii) We study the characteristics of cliques in random graphs as a function of size and density.
Advisors/Committee Members: Ryerson University (Degree grantor).
Subjects/Keywords: Random graphs; Graph theory; Algorithms; Graph 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):
Patel, S. (2010). Clique Listing Algorithms and Characteristics of Cliques in Random Graphics. (Thesis). Ryerson University. Retrieved from https://digital.library.ryerson.ca/islandora/object/RULA%3A1845
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):
Patel, Sonal. “Clique Listing Algorithms and Characteristics of Cliques in Random Graphics.” 2010. Thesis, Ryerson University. Accessed November 20, 2019.
https://digital.library.ryerson.ca/islandora/object/RULA%3A1845.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Patel, Sonal. “Clique Listing Algorithms and Characteristics of Cliques in Random Graphics.” 2010. Web. 20 Nov 2019.
Vancouver:
Patel S. Clique Listing Algorithms and Characteristics of Cliques in Random Graphics. [Internet] [Thesis]. Ryerson University; 2010. [cited 2019 Nov 20].
Available from: https://digital.library.ryerson.ca/islandora/object/RULA%3A1845.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Patel S. Clique Listing Algorithms and Characteristics of Cliques in Random Graphics. [Thesis]. Ryerson University; 2010. Available from: https://digital.library.ryerson.ca/islandora/object/RULA%3A1845
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Indiana University
24.
Firoz, Jesun Sahariar.
Synchronization-avoiding graph algorithms and runtime aspects
.
Degree: 2018, Indiana University
URL: http://hdl.handle.net/2022/22605
► Massively parallel computers provide unprecedented computing power that is only expected to grow. General-purpose Asynchronous Many-Task (AMT) runtimes exposes significant fine-grained parallelism. However, traditional Bulk-Synchronous…
(more)
▼ Massively parallel computers provide unprecedented computing power that is only expected to grow. General-purpose Asynchronous Many-Task (AMT) runtimes exposes significant fine-grained parallelism. However, traditional Bulk-Synchronous Parallel (BSP) approach and variants thereof fail to utilize the full potential of AMT runtimes. In such execution model, parallel overheads may dominate execution time and hinder performance, especially in distributed memory settings. The synchronization overhead in particular is deeply rooted in the programming practice because it makes algorithms easier to design and implement. However, irregular applications such as
graph algorithms can suffer performance bottlenecks due to the straggler effect induced by global and vertex-centric barriers. In the effort to eliminate barriers, we design and study unordered, data-driven
graph algorithms, relying on optimistic (speculative) execution. Our design of algorithms allows work to be performed in any order, refining the result as the algorithm progresses. This flexibility in ordering facilitates parallel computation without global or vertex-centric synchronization. To avoid “wasted” work, our approach relies on local work prioritization. However, performance of such algorithms is marred by two competing trends: on one hand, there is a substantial level of parallelism, which, on the other hand, necessitates runtime support with potentially high overhead and scheduling complexity. Specifically, the global work order obtained by local prioritization is susceptible to the interference from the runtime. As such, we also investigate important runtime aspects that influence the performance of
graph algorithms. In particular, we study the interaction between default runtime scheduling policies and synchronization-avoiding distributed
graph algorithms. We propose plug-in scheduling policies in the application-layer for speculative
graph algorithms that can provide feedback to the runtime to adjust the network progress frequency and flow of messages to the remote destinations. These techniques are useful for unordered distributed
graph algorithms that necessitate a balanced interleaving of communication and computation to achieve better performance.
Graph algorithms designed in different programming models have vastly different workload characteristics. In the final part of the thesis, we propose adaptivity of the runtime parameters such as message coalescing and flow control to adjust the “pressure points” in the runtime due to variable workload characteristics over the execution of an algorithm.
Advisors/Committee Members: Lumsdaine, Andrew (advisor).
Subjects/Keywords: Distributed Graph Algorithms;
Distributed Runtimes;
Graph 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):
Firoz, J. S. (2018). Synchronization-avoiding graph algorithms and runtime aspects
. (Thesis). Indiana University. Retrieved from http://hdl.handle.net/2022/22605
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):
Firoz, Jesun Sahariar. “Synchronization-avoiding graph algorithms and runtime aspects
.” 2018. Thesis, Indiana University. Accessed November 20, 2019.
http://hdl.handle.net/2022/22605.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Firoz, Jesun Sahariar. “Synchronization-avoiding graph algorithms and runtime aspects
.” 2018. Web. 20 Nov 2019.
Vancouver:
Firoz JS. Synchronization-avoiding graph algorithms and runtime aspects
. [Internet] [Thesis]. Indiana University; 2018. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/2022/22605.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Firoz JS. Synchronization-avoiding graph algorithms and runtime aspects
. [Thesis]. Indiana University; 2018. Available from: http://hdl.handle.net/2022/22605
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Victoria
25.
Manzer, Joshua Daniel Adrian.
Chronological rectangle digraphs.
Degree: Department of Mathematics and Statistics, 2015, University of Victoria
URL: http://hdl.handle.net/1828/6989
► Interval graphs admit elegant ordering and structural characterizations. A natural digraph analogue of interval graphs, called chronological interval digraphs, has recently been identified and studied.…
(more)
▼ Interval graphs admit elegant ordering and structural characterizations. A natural digraph analogue of interval graphs, called chronological interval digraphs, has recently been identified and studied.
We introduce the class of chronological rectangle digraphs, and show that they are a higher dimensional analogue of chronological interval digraphs. A main goal of this thesis is to establish a foundation of knowledge about this class, including basic properties and an ordering characterization. Our most significant result is a forbidden induced subdigraph characterization for the series-parallel digraphs which are chronological rectangle. We also discuss obtaining chronological rectangle digraphs from orientations of graphs.
In addition we introduce the related concept of the chronological interval dimension of a digraph, and determine the digraphs for which it is defined. Unit and proper chronological rectangle digraphs, defined analogously to unit and proper interval graphs, are also introduced and studied.
Advisors/Committee Members: Huang, Jing (supervisor).
Subjects/Keywords: Mathematics; Combinatorics; Graph Theory; Structural 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):
Manzer, J. D. A. (2015). Chronological rectangle digraphs. (Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/6989
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):
Manzer, Joshua Daniel Adrian. “Chronological rectangle digraphs.” 2015. Thesis, University of Victoria. Accessed November 20, 2019.
http://hdl.handle.net/1828/6989.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Manzer, Joshua Daniel Adrian. “Chronological rectangle digraphs.” 2015. Web. 20 Nov 2019.
Vancouver:
Manzer JDA. Chronological rectangle digraphs. [Internet] [Thesis]. University of Victoria; 2015. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/1828/6989.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Manzer JDA. Chronological rectangle digraphs. [Thesis]. University of Victoria; 2015. Available from: http://hdl.handle.net/1828/6989
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Delft University of Technology
26.
Penders, A.
Accelerating Graph Analysis with Heterogeneous Systems:.
Degree: 2012, Delft University of Technology
URL: http://resolver.tudelft.nl/uuid:7f3eeb52-77bd-4fdb-84a9-ea9ca0a35b94
► Data analysis is a rising field of interest for computer science research due to the growing amount of information that is digitally available. This increase…
(more)
▼ Data analysis is a rising field of interest for computer science research due to the growing amount of information that is digitally available. This increase in data has as direct consequence that any analysis is significantly complex. By using structured representations for the data sets, like graphs, the analysis becomes feasible, but is still time-consuming. In this project, the focus is on the reduction of the computational time for data analysis, with the introduction of accelerators.
Accelerators are specialized hardware components that assist the general processing unit in performing (parts of) the task at hand. In particular, we focus on the use of General Purpose Graphical Processing Units (GPGPU) to help speedup the analysis. GPUs are specifically designed for representing and manipulating graphical data which invoke the processing of large chunks of data, GPUs are designed with large numbers of concurrent processing units and thus have a high potential of improving performance.
In this project, we show the impact of using GPGPUs for both simple and more complex analysis, varying from small to large data sets, with the use of a programming model called OpenCL. We compare the performance of using accelerators against the traditional CPU-based implementation. Due to the inter-platform portability of the OpenCL model, such comparison can be performed without having to alter the algorithm.
The use of accelerators is expected to become beneficial for analysis that require large computational power. For example, search algorithms (that require little to no computation) are not expected to profit from accelerators, while the more complex, centrality analysis is expected to have significantly more benefit from accelerators. Our results clearly shows this shift of performance improvement when algorithms further utilize the potential of accelerators, because the analysis grows in size and/ or complexity.
Advisors/Committee Members: Varbanescu, A.L..
Subjects/Keywords: GPU; graph; Graph analysis; accelerators; OpenCL; parallel
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):
Penders, A. (2012). Accelerating Graph Analysis with Heterogeneous Systems:. (Masters Thesis). Delft University of Technology. Retrieved from http://resolver.tudelft.nl/uuid:7f3eeb52-77bd-4fdb-84a9-ea9ca0a35b94
Chicago Manual of Style (16th Edition):
Penders, A. “Accelerating Graph Analysis with Heterogeneous Systems:.” 2012. Masters Thesis, Delft University of Technology. Accessed November 20, 2019.
http://resolver.tudelft.nl/uuid:7f3eeb52-77bd-4fdb-84a9-ea9ca0a35b94.
MLA Handbook (7th Edition):
Penders, A. “Accelerating Graph Analysis with Heterogeneous Systems:.” 2012. Web. 20 Nov 2019.
Vancouver:
Penders A. Accelerating Graph Analysis with Heterogeneous Systems:. [Internet] [Masters thesis]. Delft University of Technology; 2012. [cited 2019 Nov 20].
Available from: http://resolver.tudelft.nl/uuid:7f3eeb52-77bd-4fdb-84a9-ea9ca0a35b94.
Council of Science Editors:
Penders A. Accelerating Graph Analysis with Heterogeneous Systems:. [Masters Thesis]. Delft University of Technology; 2012. Available from: http://resolver.tudelft.nl/uuid:7f3eeb52-77bd-4fdb-84a9-ea9ca0a35b94
University of Melbourne
27.
Rotheram, Ricky.
Cores of vertex-transitive graphs.
Degree: 2013, University of Melbourne
URL: http://hdl.handle.net/11343/39734
► The core of a graph Γ is the smallest graph Γ^\ast for which there exist graph homomorphisms Γ → Γ^\ast and Γ^\ast → Γ. Thus cores are fundamental to…
(more)
▼ The core of a graph Γ is the smallest graph Γ^\ast for which there exist graph homomorphisms Γ → Γ^\ast and Γ^\ast → Γ. Thus cores are fundamental to our understanding of general graph homomorphisms. It is known that for a vertex-transitive graph Γ, Γ^\ast is vertex-transitive, and that ≤ ft|V(Γ^\ast))| divides ≤ ft|V(Γ))|. The purpose of this thesis is to determine the cores of various families of vertex-transitive and symmetric graphs.
We focus primarily on finding the cores of imprimitive symmetric graphs of order pq, where p<q are primes. We choose to investigate these graphs because their cores must be symmetric graphs with ≤ ft|V(Γ^\ast))|=pnormal{ or }q. These graphs have been completely classified, and are split into three broad families, namely the circulants, the incidence graphs and the Maru\v{s}i\v{c}-Scapellato graphs. We use this classification to determine the cores of all imprimitive symmetric graphs of order pq, using different approaches for the circulants, the incidence graphs and the Maru\v{s}i\v{c}-Scapellato graphs.
Circulant graphs are examples of Cayley graphs of abelian groups. Thus, we generalise the approach used to determine the cores of the symmetric circulants of order pq, and apply it to other Cayley graphs of abelian groups. Doing this, we show that if Γ is a Cayley graph of an abelian group, then \Aut(Γ^\ast) contains a transitive subgroup generated by semiregular automorphisms, and either Γ^\ast is an odd cycle or girth (Γ^\ast) ≤ 4. Consequently, we show that Γ^\ast is not a cubic symmetric graph (unless Γ^\ast\cong K4) or 3-arc-transitive (unless Γ^\ast is an odd cycle). We also provide a partial confirmation of a conjecture by Samal, on the cores of Cayley graphs of elementary abelian groups.
Subjects/Keywords: repository; mathematics; graph theory; algebraic 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):
Rotheram, R. (2013). Cores of vertex-transitive graphs. (Masters Thesis). University of Melbourne. Retrieved from http://hdl.handle.net/11343/39734
Chicago Manual of Style (16th Edition):
Rotheram, Ricky. “Cores of vertex-transitive graphs.” 2013. Masters Thesis, University of Melbourne. Accessed November 20, 2019.
http://hdl.handle.net/11343/39734.
MLA Handbook (7th Edition):
Rotheram, Ricky. “Cores of vertex-transitive graphs.” 2013. Web. 20 Nov 2019.
Vancouver:
Rotheram R. Cores of vertex-transitive graphs. [Internet] [Masters thesis]. University of Melbourne; 2013. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/11343/39734.
Council of Science Editors:
Rotheram R. Cores of vertex-transitive graphs. [Masters Thesis]. University of Melbourne; 2013. Available from: http://hdl.handle.net/11343/39734
Oklahoma State University
28.
Konduri, Shyamprasad.
Coordination of Multiple Autonomous Vehicles with Directed Communication Graphs.
Degree: Mechanical & Aerospace Engineering, 2012, Oklahoma State University
URL: http://hdl.handle.net/11244/9970
► A considerable amount of research has been conducted on coordination control of vehicle formations in the last few decades due to its possible applications in…
(more)
▼ A considerable amount of research has been conducted on coordination control of vehicle formations in the last few decades due to its possible applications in numerous areas, such as patrolling, search and rescue, vehicle platoons, etc. Information flow between vehicles is vital for the formation to function properly. Controllability and stability of the formation depends on the type of information flow that is employed between vehicles. This work focuses on using a type of directed communication
graph, called the ring
graph, for coordination control of vehicle platoons. A detailed study of literature is undertaken to clearly understand the limitations of the various types of undirected graphs in terms of stability and scalability. The use of ring
graph in vehicle platoons is investigated. The problems associated with the ring
graph in its basic form related to communication sensor range and the scalability of ring
graph are investigated. Methods to create a ring
graph topology that requires minimal communication distance over a given formation are also investigated. A survey of literature was undertaken to investigate the formulation of the Traveling Salesman Problem (TSP), constraints involved in TSP, methods to solve TSP including exact and approximate algorithms. The problem of finding a ring
graph for a given vehicle formation is addressed by formulating this problem as a special case of the TSP. Properties such as stability and scalability of the formation with a controller based on the ring
graph are studied. Lack of scalability of the controller that is based on the ring
graph is discussed. Alternate ring
graph topologies which address the practical issues such as communication range of transmitters are proposed. Simulations which show that the alternate ring graphs have similar properties as the basic ring
graph are carried out. Controller based on multiple ring graphs on a vehicle platoon and its advantages over the single ring topologies are studied. An algorithm based on the branch and bound method is proposed to solve the modified TSP and to generate a ring
graph for the given vehicle platoons, or two- and three-dimensional vehicle formations. An experimental platform consisting of multiple homogeneous autonomous robots is developed. A coordination controller using ring
graph is implemented on the experimental platform and results for a number of platoon initial condition scenarios are presented.
Advisors/Committee Members: Pagilla, Prabhakar R. (advisor), Young, Gary E. (committee member), Arena, Andrew S. (committee member).
Subjects/Keywords: coordination; directed graph; ring graph; vehicle platoon
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):
Konduri, S. (2012). Coordination of Multiple Autonomous Vehicles with Directed Communication Graphs. (Thesis). Oklahoma State University. Retrieved from http://hdl.handle.net/11244/9970
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):
Konduri, Shyamprasad. “Coordination of Multiple Autonomous Vehicles with Directed Communication Graphs.” 2012. Thesis, Oklahoma State University. Accessed November 20, 2019.
http://hdl.handle.net/11244/9970.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Konduri, Shyamprasad. “Coordination of Multiple Autonomous Vehicles with Directed Communication Graphs.” 2012. Web. 20 Nov 2019.
Vancouver:
Konduri S. Coordination of Multiple Autonomous Vehicles with Directed Communication Graphs. [Internet] [Thesis]. Oklahoma State University; 2012. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/11244/9970.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Konduri S. Coordination of Multiple Autonomous Vehicles with Directed Communication Graphs. [Thesis]. Oklahoma State University; 2012. Available from: http://hdl.handle.net/11244/9970
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Waterloo
29.
Derka, Martin.
Restricted String Representations.
Degree: 2017, University of Waterloo
URL: http://hdl.handle.net/10012/12253
► A string representation of a graph assigns to every vertex a curve in the plane so that two curves intersect if and only if the…
(more)
▼ A string representation of a graph assigns to every vertex a curve in the plane so that two curves intersect if and only if the represented vertices are adjacent. This work investigates string representations of graphs with an emphasis on the shapes of curves and the way they intersect. We strengthen some previously known results and show that every planar graph
has string representations where every curve consists of axis-parallel line segments with at most two bends (those are the so-called B2-VPG representations) and simultaneously two curves intersect each other at most once (those are the
so-called 1-string representations). Thus, planar graphs are B2-VPG 1-string graphs. We further show that with some restrictions on the shapes of the curves, string representations can be used to produce approximation algorithms for several hard problems. The B2-VPG representations of planar graphs satisfy these restrictions. We attempt to further
restrict the number of bends in VPG representations for subclasses of planar graphs, and investigate B1-VPG
representations. We propose new classes of string representations for planar graphs that we call ``order-preserving.'' Order-preservation is an interesting property which relates the string representation to the planar embedding of the graph, and we believe that it might prove useful when constructing string representations. Finally, we extend our investigation
of string representations to string representations that require some curves to intersect multiple times. We show that there are outer-string graphs that require an exponential number of crossings in their outer-string representations. Our construction also proves that 1-planar graphs, i.e., graphs that are no longer planar, yet fairly close to planar graphs, may have string representations, but they are not always 1-string.
Subjects/Keywords: string representation; B2-VPG graph; string graph
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):
Derka, M. (2017). Restricted String Representations. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/12253
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):
Derka, Martin. “Restricted String Representations.” 2017. Thesis, University of Waterloo. Accessed November 20, 2019.
http://hdl.handle.net/10012/12253.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Derka, Martin. “Restricted String Representations.” 2017. Web. 20 Nov 2019.
Vancouver:
Derka M. Restricted String Representations. [Internet] [Thesis]. University of Waterloo; 2017. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/10012/12253.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Derka M. Restricted String Representations. [Thesis]. University of Waterloo; 2017. Available from: http://hdl.handle.net/10012/12253
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
University of Waterloo
30.
Zhang, Yan.
Efficient Structure-aware OLAP Query Processing over Large Property Graphs.
Degree: 2017, University of Waterloo
URL: http://hdl.handle.net/10012/12724
► Property graph model is a semantically rich model for real-world applications that represent their data as graphs, e.g., communication networks, social networks, financial transaction networks.…
(more)
▼ Property graph model is a semantically rich model for real-world applications that represent their data as graphs, e.g., communication networks, social networks, financial transaction networks. On-Line Analytical Processing (OLAP) provides an important tool for data analysis by allowing users to perform data aggregation through different combinations of dimensions. For example, given a Q&A forum dataset, in order to study if there is a correlation between a poster's age and his or her post quality, one may ask what is the average age of users grouped by the post score. Another example is that, in the field of music industry, it may be interesting to ask what total sales of records are with respect to different music companies and years so as to conduct a market activity analysis. Surprisingly, current graph databases do not efficiently support OLAP aggregation queries. In most cases, such queries are transformed to a sequence of join operations, and the system computes everything from scratch. For example, Neo4j, a state-of-art graph database system, processes each OLAP query in two steps. First, it expands the nodes and edges that satisfy the given query constraint. Then it performs the aggregation over all the valid substructures returned from the first step. However, in data warehousing workloads, it is common to have repeated queries from time to time. Computing everything from scratch would be highly inefficient. Materialization and view maintenance techniques developed in traditional RDBMS have proved to be efficient for processing OLAP workloads. Following the generic materialization methodology, in this thesis we develop a structure-aware cuboid caching solution to efficiently support OLAP aggregation queries over property graphs. Structure-aware means that our solution takes both heterogeneous attributes and graph topological information into consideration. The essential idea is to precompute and materialize some views based on statistics of history workload, such that future query processing can be accelerated.
We implement a prototype system on top of Neo4j. Empirical studies over real-world property graphs show that, with a reasonable space cost constraint, our solution on average achieves 15-30x speedup over native Neo4j in time efficiency.
Subjects/Keywords: OLAP; Graph Database; Property Graph; Materialized View
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):
Zhang, Y. (2017). Efficient Structure-aware OLAP Query Processing over Large Property Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/12724
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):
Zhang, Yan. “Efficient Structure-aware OLAP Query Processing over Large Property Graphs.” 2017. Thesis, University of Waterloo. Accessed November 20, 2019.
http://hdl.handle.net/10012/12724.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
MLA Handbook (7th Edition):
Zhang, Yan. “Efficient Structure-aware OLAP Query Processing over Large Property Graphs.” 2017. Web. 20 Nov 2019.
Vancouver:
Zhang Y. Efficient Structure-aware OLAP Query Processing over Large Property Graphs. [Internet] [Thesis]. University of Waterloo; 2017. [cited 2019 Nov 20].
Available from: http://hdl.handle.net/10012/12724.
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
Council of Science Editors:
Zhang Y. Efficient Structure-aware OLAP Query Processing over Large Property Graphs. [Thesis]. University of Waterloo; 2017. Available from: http://hdl.handle.net/10012/12724
Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation
◁ [1] [2] [3] [4] [5] … [142] ▶
. 
Open Access Theses and Dissertations