subject:(Graphs)

1. Arvind, N R. Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs; -.

Degree: Mathematical Science, 2010, INFLIBNET

URL: http://shodhganga.inflibnet.ac.in/handle/10603/4726

►

This thesis deals mainly with two related coloring problems ? forbidden subgraph colorings and oriented colorings. The former deals with proper colorings of vertices or… (more)

▼

This thesis deals mainly with two related coloring problems ? forbidden subgraph colorings and oriented colorings. The former deals with proper colorings of vertices or edges of a graph with constraints on the union of color classes. A well-known example is the acyclic vertex coloring in which we require a proper coloring such that the union of any two color classes is acyclic. Other wellstudied examples include the acyclic edge coloring and star coloring. Our focus in this thesis is a generalization of these special types of colorings. Oriented coloring deals with colorings of oriented graphs (directed graphs obtained by orienting each edge of a simple undirected graph). Specifically, an oriented coloring is a homomorphism to an oriented graph, the vertices of the target graph being considered as the colors assigned to the vertices of the source graph. For both of these problems, we want to find good upper bounds for the number of colors required for such colorings. In this thesis, we find upper bounds for forbidden subgraph chromatic numbers in terms of the maximum degree. For the union of two color classes, we show the asymptotic tightness of our bounds by a probabilistic contstruction. We then show that the oriented chromatic number of a graph can be bounded in terms of the forbidden subgraph chromatic numbers. In conjunction with our afore-mentioned results, this allowed us to prove improved bounds on oriented chromatic numbers of graphs on surfaces. Specifically, we obtained the following results: ? Given a family F of connected graphs each having at least m edges, the vertices of any graph ofmaximum degree _ can be properly colored using O(_1+ 1 mand#8722;1 ) colors so that in the union of any 2 color classes, there is no copy of H for any H and#8712; F. ? Any graph of genus g has oriented chromatic number at most 2g1/2+o(1) . We also consider edge colorings of graphs with restrictions on the union of color classes. While edge colorings can simply be considered as vertex colorings of the line graph.

Bibilography p.95-101

Advisors/Committee Members: Balasubramanian R, Subramanian, C R.

Subjects/Keywords: Graphs; Graphs dimensions; Graphs colorings

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Arvind, N. R. (2010). Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs; -. (Thesis). INFLIBNET. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/4726

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Arvind, N R. “Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs; -.” 2010. Thesis, INFLIBNET. Accessed February 27, 2020. http://shodhganga.inflibnet.ac.in/handle/10603/4726.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Arvind, N R. “Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs; -.” 2010. Web. 27 Feb 2020.

Vancouver:

Arvind NR. Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs; -. [Internet] [Thesis]. INFLIBNET; 2010. [cited 2020 Feb 27]. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/4726.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Arvind NR. Forbidden subgraph colorings, oriented colorings and intersection dimensions of graphs; -. [Thesis]. INFLIBNET; 2010. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/4726

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Western Australia

2. Amarra, Maria Carmen. Symmetric graphs of diameter two.

Degree: PhD, 2012, University of Western Australia

URL: http://repository.uwa.edu.au:80/R/?func=dbin-jump-full&object_id=33953&local_base=GEN01-INS01

►

A graph Γ is G-symmetric if it admits an arc-transitive subgroup G of automorphisms, and has diameter 2 if it is not a complete graph… (more)

▼

A graph Γ is G-symmetric if it admits an arc-transitive subgroup G of automorphisms, and has diameter 2 if it is not a complete graph (that is, it has at least one pair of nonadjacent vertices) and if any two nonadjacent vertices have a common neighbour. Using normal quotient analysis, the study of G-symmetric diameter 2 graphs can be reduced to the following cases: (i) All nontrivial G-normal quotient graphs of Γ are complete graphs. (ii) All nontrivial normal subgroups of G act transitively on the vertex set of Γ. We consider in detail the pairs (Γ,G) that satisfy (i) where Γ may have diameter greater than two, as well as those that satisfy (ii) where Γ has diameter 2 and G is maximal in the symmetric group of the vertex set of Γ subject to being non-2-transitive. For the first case, we show that if Γ has at least three nontrivial normal quotients, then G corresponds to a finite transitive linear group H and Γ can be constructed from the natural vector space of H. We classify all connected graphs arising from groups H which are not subgroups of a one-dimensional affine group, and identify those which have diameter greater than two. For the second case, the group G is given by C. E. Praeger's classification of quasiprimitive permutation groups, and we focus on the subcase where G is of affine type. Such groups G correspond to irreducible subgroups of the general linear group which, in turn, have been classified by M. Aschbacher. Moreover, a uniform construction for Γ is known, so it only remains to determine which graphs have diameter 2. Using a case-by-case analysis, we are able to classify all diameter 2 graphs for some of the Aschbacher classes; in the others we determine bounds on certain parameters in order to have diameter 2, which reduce the number of unresolved cases.

A graph Γ is G-symmetric if it admits an arc-transitive subgroup G of automorphisms, and has diameter 2 if it is not a complete graph (that is, it has at least one pair of nonadjacent vertices) and if any two nonadjacent vertices have a common neighbour. Using normal quotient analysis, the study of G-symmetric diameter 2 graphs can be reduced to the following cases: (i) All nontrivial G-normal quotient graphs of Γ are complete graphs. (ii) All nontrivial normal subgroups of G act transitively on the vertex set of Γ. We consider in detail the pairs (Γ,G) that satisfy (i) where Γ may have diameter greater than two, as well as those that satisfy (ii) where Γ has diameter 2 and G is maximal in the symmetric group of the vertex set of Γ subject to being non-2-transitive. For the first case, we show that if Γ has at least three nontrivial normal quotients, then G corresponds to a finite transitive linear group H and Γ can be constructed from the natural vector space of H. We classify all connected graphs arising from groups H which are not subgroups of a one-dimensional affine group, and identify those which have diameter greater than two. For the second case, the group G is given by C. E. Praeger's classification of quasiprimitive permutation…

Subjects/Keywords: Systematic graphs; Diameter two graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Amarra, M. C. (2012). Symmetric graphs of diameter two. (Doctoral Dissertation). University of Western Australia. Retrieved from http://repository.uwa.edu.au:80/R/?func=dbin-jump-full&object_id=33953&local_base=GEN01-INS01

Chicago Manual of Style (16^th Edition):

Amarra, Maria Carmen. “Symmetric graphs of diameter two.” 2012. Doctoral Dissertation, University of Western Australia. Accessed February 27, 2020. http://repository.uwa.edu.au:80/R/?func=dbin-jump-full&object_id=33953&local_base=GEN01-INS01.

MLA Handbook (7^th Edition):

Amarra, Maria Carmen. “Symmetric graphs of diameter two.” 2012. Web. 27 Feb 2020.

Vancouver:

Amarra MC. Symmetric graphs of diameter two. [Internet] [Doctoral dissertation]. University of Western Australia; 2012. [cited 2020 Feb 27]. Available from: http://repository.uwa.edu.au:80/R/?func=dbin-jump-full&object_id=33953&local_base=GEN01-INS01.

Council of Science Editors:

Amarra MC. Symmetric graphs of diameter two. [Doctoral Dissertation]. University of Western Australia; 2012. Available from: http://repository.uwa.edu.au:80/R/?func=dbin-jump-full&object_id=33953&local_base=GEN01-INS01

University of Georgia

3. Che, Dongsheng. Computational methods for deciphering genomic structures in prokaryotes.

Degree: PhD, Computer Science, 2008, University of Georgia

URL: http://purl.galileo.usg.edu/uga_etd/che_dongsheng_200808_phd

► High-throughput sequencing technologies have generated huge amounts of genomic data. This wealth of genomic data provides computational biologists unprecedented opportunities to unveil the biological machinery… (more)

▼ High-throughput sequencing technologies have generated huge amounts of genomic data. This wealth of genomic data provides computational biologists unprecedented opportunities to unveil the biological machinery encoded in genomes. Characterizing the structure of genomes is an important and challenging task; it is an essential step towards deciphering the networks and pathways in a biological system. The characterization of microbial genomic structures includes: (1) identifying neighboring genes that are co-transcribed (also known as operons); (2) identifying groups of operons with evolutionary relationships (also known as uber-operons); and, (3) elucidating higher level structures that share common regulatory controls, including protein-DNA binding events and cis-regulatory elements among operons (also known as regulons). The primary goal of this thesis is to develop computational methods for elucidating the above three categories of genomic structures in prokaryotes. UNIPOP, a maximum bipartite matching-based algorithm, is designed and implemented to predict operon structures of any prokaryotic genome, without relying on experimental data or training data. The prediction accuracy of UNIPOP is shown to be superior to most other operon predictors when evaluating two well-studied organisms. The evolutionary relationships among operons are elucidated by using comparative genomic data and a maximum matching-based algorithm. The comparative study of uberoperons and regulons has shown that they are highly related, indicating the effectiveness of using uber-operons for predicting regulons. With the availability of predicted operons, we propose an approach, phylogenetic footprinting for prokaryotes, to study cis regulatory motifs in the promoter regions of operons. By integrating the motif data with uber-operon data, and formulating it as a graph partitioning problem, we predicted regulons in Escherichia coli K12. Different sources of validation have shown that our predicted regulons were consistent with the data of known regulons, functional relatedness and expression data. More importantly, we have also derived some novel regulons which were biologically meaningful. In summary, we predict different levels of genomic structures by developing novel graphtheoretic based algorithms and using comparative genomic analysis. Our methods are universally applicable to all sequenced microbial genomes, and outperform most of the other published methods in terms of prediction accuracy. Our prediction tools can provide assistance in understanding the machinery of gene regulation, biological networks and pathways. Advisors/Committee Members: Liming Cai.

Subjects/Keywords: Bipartite graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Che, D. (2008). Computational methods for deciphering genomic structures in prokaryotes. (Doctoral Dissertation). University of Georgia. Retrieved from http://purl.galileo.usg.edu/uga_etd/che_dongsheng_200808_phd

Chicago Manual of Style (16^th Edition):

Che, Dongsheng. “Computational methods for deciphering genomic structures in prokaryotes.” 2008. Doctoral Dissertation, University of Georgia. Accessed February 27, 2020. http://purl.galileo.usg.edu/uga_etd/che_dongsheng_200808_phd.

MLA Handbook (7^th Edition):

Che, Dongsheng. “Computational methods for deciphering genomic structures in prokaryotes.” 2008. Web. 27 Feb 2020.

Vancouver:

Che D. Computational methods for deciphering genomic structures in prokaryotes. [Internet] [Doctoral dissertation]. University of Georgia; 2008. [cited 2020 Feb 27]. Available from: http://purl.galileo.usg.edu/uga_etd/che_dongsheng_200808_phd.

Council of Science Editors:

Che D. Computational methods for deciphering genomic structures in prokaryotes. [Doctoral Dissertation]. University of Georgia; 2008. Available from: http://purl.galileo.usg.edu/uga_etd/che_dongsheng_200808_phd

University of Georgia

4. Rath, Bijaya. Generation of non-isomorphic cubic Cayley graphs.

Degree: MS, Computer Science, 2010, University of Georgia

URL: http://purl.galileo.usg.edu/uga_etd/rath_bijaya_201012_ms

► This thesis investigates the generation of non-isomorphic simple cubic Cayley graphs. The research is motivated indirectly by the long standing conjecture that all Cayley graphs… (more)

Subjects/Keywords: Cayley graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Rath, B. (2010). Generation of non-isomorphic cubic Cayley graphs. (Masters Thesis). University of Georgia. Retrieved from http://purl.galileo.usg.edu/uga_etd/rath_bijaya_201012_ms

Chicago Manual of Style (16^th Edition):

Rath, Bijaya. “Generation of non-isomorphic cubic Cayley graphs.” 2010. Masters Thesis, University of Georgia. Accessed February 27, 2020. http://purl.galileo.usg.edu/uga_etd/rath_bijaya_201012_ms.

MLA Handbook (7^th Edition):

Rath, Bijaya. “Generation of non-isomorphic cubic Cayley graphs.” 2010. Web. 27 Feb 2020.

Vancouver:

Rath B. Generation of non-isomorphic cubic Cayley graphs. [Internet] [Masters thesis]. University of Georgia; 2010. [cited 2020 Feb 27]. Available from: http://purl.galileo.usg.edu/uga_etd/rath_bijaya_201012_ms.

Council of Science Editors:

Rath B. Generation of non-isomorphic cubic Cayley graphs. [Masters Thesis]. University of Georgia; 2010. Available from: http://purl.galileo.usg.edu/uga_etd/rath_bijaya_201012_ms

University of Georgia

5. Cinkir, Zubeyir. The tau constant of metrized graphs.

Degree: PhD, Mathematics, 2007, University of Georgia

URL: http://purl.galileo.usg.edu/uga_etd/cinkir_zubeyir_200708_phd

► Metrized graphs, which are in 1−1 correspondence with weighted graphs, were introduced by R. Rumely in order to study arithmetic properties of curves. “Reduction graphs”,… (more)

▼ Metrized graphs, which are in 1−1 correspondence with weighted graphs, were introduced by R. Rumely in order to study arithmetic properties of curves. “Reduction graphs”, the dual graphs associated to the special fibre curve, are examples of metrized graphs. Rumely and T. Chinburg used metrized graphs in their work on the “capacity pairing”. Later, S. Zhang, in his work on “admissible pairing on curves”, demonstrated the important role of metrized graphs in the proof of Bogomolov’s conjecture in the case of bad reductions. The diagonal value of the Arakelov-Green’s function gμcan(x, y) on a metrized graph 􀀀 is a constant for a certain “canonical measure” μcan studied by Rumely and Chinburg on a metrized graph 􀀀. This constant is called the “tau constant”, and was denoted τ (􀀀), by M.Baker and Rumely, who studied it in their Summer 2003 REU at UGA. There are a number of ways to describe τ (􀀀). In terms of spectral theory, it is the trace of the inverse of the Laplacian on 􀀀 with respect to μcan. Also, it is closely related to the resistance and the voltage functions on 􀀀, when 􀀀 is considered as an electrical network. Our main focus in this thesis is to show the existence of a universal positive lower bound to τ (􀀀) for any 􀀀 with length(􀀀)=1. This is not completely achieved, but we prove it in important cases and we develop a systematic theory of the tau constant. We give new interpretations of the canonical measure μcan in terms of the voltage functions on 􀀀. These enable us to obtain new formulas for τ (􀀀). We show how τ (􀀀) changes under various graph operations including doubling edges, deleting and contracting edges, and taking unions of graphs along one or two points. We establish some identities which we call the “deletion”, “contraction”, and “deletion-contraction” identities. We show that τ (􀀀) ≥ length(􀀀)·(1− 4 )2 12 , if the edge connectivity λ satisfies λ > 4.We show how τ (􀀀) is related to the discrete Laplacian.We present Maple codes and effective Matlab codes for computing τ (􀀀). We also present several families of graphs with equal edge lengths and having tau constants apparently approaching to the value length(􀀀)/108, which we conjecture to be the minimal possible value. By using the properties of discrete Laplacian, we give new proofs of Foster’s identities for electrical networks, and generalize them. We show, as an application, that there is an explicit relation between τ (􀀀) and the effective generalized Bogomolov’s conjectures over global fields. Advisors/Committee Members: Robert Rumely.

Subjects/Keywords: Metrized graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Cinkir, Z. (2007). The tau constant of metrized graphs. (Doctoral Dissertation). University of Georgia. Retrieved from http://purl.galileo.usg.edu/uga_etd/cinkir_zubeyir_200708_phd

Chicago Manual of Style (16^th Edition):

Cinkir, Zubeyir. “The tau constant of metrized graphs.” 2007. Doctoral Dissertation, University of Georgia. Accessed February 27, 2020. http://purl.galileo.usg.edu/uga_etd/cinkir_zubeyir_200708_phd.

MLA Handbook (7^th Edition):

Cinkir, Zubeyir. “The tau constant of metrized graphs.” 2007. Web. 27 Feb 2020.

Vancouver:

Cinkir Z. The tau constant of metrized graphs. [Internet] [Doctoral dissertation]. University of Georgia; 2007. [cited 2020 Feb 27]. Available from: http://purl.galileo.usg.edu/uga_etd/cinkir_zubeyir_200708_phd.

Council of Science Editors:

Cinkir Z. The tau constant of metrized graphs. [Doctoral Dissertation]. University of Georgia; 2007. Available from: http://purl.galileo.usg.edu/uga_etd/cinkir_zubeyir_200708_phd

6. Mozes, Shay. Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs.

Degree: PhD, Computer Science, 2013, Brown University

URL: https://repository.library.brown.edu/studio/item/bdr:320482/

► Large graphs are ubiquitous in many diverse fields ranging from sociology and economics to biology and engineering. Applications in numerous areas such as transportation, geographical… (more)

Subjects/Keywords: planar graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Mozes, S. (2013). Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs. (Doctoral Dissertation). Brown University. Retrieved from https://repository.library.brown.edu/studio/item/bdr:320482/

Chicago Manual of Style (16^th Edition):

Mozes, Shay. “Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs.” 2013. Doctoral Dissertation, Brown University. Accessed February 27, 2020. https://repository.library.brown.edu/studio/item/bdr:320482/.

MLA Handbook (7^th Edition):

Mozes, Shay. “Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs.” 2013. Web. 27 Feb 2020.

Vancouver:

Mozes S. Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs. [Internet] [Doctoral dissertation]. Brown University; 2013. [cited 2020 Feb 27]. Available from: https://repository.library.brown.edu/studio/item/bdr:320482/.

Council of Science Editors:

Mozes S. Efficient Algorithms for Shortest-Path and Maximum-Flow Problems in Planar Graphs. [Doctoral Dissertation]. Brown University; 2013. Available from: https://repository.library.brown.edu/studio/item/bdr:320482/

Rutgers University

7. Baron, Jacob D., 1988-. Two problems on cycles in random graphs.

Degree: PhD, Mathematics, 2016, Rutgers University

URL: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/

►

We prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of… (more)

Subjects/Keywords: Random graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Baron, Jacob D., 1. (2016). Two problems on cycles in random graphs. (Doctoral Dissertation). Rutgers University. Retrieved from https://rucore.libraries.rutgers.edu/rutgers-lib/51229/

Chicago Manual of Style (16^th Edition):

Baron, Jacob D., 1988-. “Two problems on cycles in random graphs.” 2016. Doctoral Dissertation, Rutgers University. Accessed February 27, 2020. https://rucore.libraries.rutgers.edu/rutgers-lib/51229/.

MLA Handbook (7^th Edition):

Baron, Jacob D., 1988-. “Two problems on cycles in random graphs.” 2016. Web. 27 Feb 2020.

Vancouver:

Baron, Jacob D. 1. Two problems on cycles in random graphs. [Internet] [Doctoral dissertation]. Rutgers University; 2016. [cited 2020 Feb 27]. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/.

Council of Science Editors:

Baron, Jacob D. 1. Two problems on cycles in random graphs. [Doctoral Dissertation]. Rutgers University; 2016. Available from: https://rucore.libraries.rutgers.edu/rutgers-lib/51229/

8. Camarero Coterillo, Cristobal. Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.

Degree: 2015, Universidad de Cantabria

URL: http://hdl.handle.net/10902/6542

► ABSTRACT: The topology of a interconnection network is the graph of its routers. The topologies that are being currently used in large supercomputers can be… (more)

Subjects/Keywords: Graphs

…brings the definition of lattice graphs, which actually contains all Cayley graphs over Abelian… …used in crystallography. When these are used to define lattice graphs, good properties are… …machines. From the properties of these crystal lattice graphs the symmetry is very notable; it is… …obtained that symmetric lattice graphs have better performance than the asymmetric ones. This… …implement them in racks. Although there are known families of graphs with better distance…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Camarero Coterillo, C. (2015). Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. (Doctoral Dissertation). Universidad de Cantabria. Retrieved from http://hdl.handle.net/10902/6542

Chicago Manual of Style (16^th Edition):

Camarero Coterillo, Cristobal. “Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.” 2015. Doctoral Dissertation, Universidad de Cantabria. Accessed February 27, 2020. http://hdl.handle.net/10902/6542.

MLA Handbook (7^th Edition):

Camarero Coterillo, Cristobal. “Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos.” 2015. Web. 27 Feb 2020.

Vancouver:

Camarero Coterillo C. Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. [Internet] [Doctoral dissertation]. Universidad de Cantabria; 2015. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/10902/6542.

Council of Science Editors:

Camarero Coterillo C. Distance and symmetry properties of graphs and their application to interconnection networks and codes: Propiedades de distancia y simetría en grafos y su aplicación a redes de interconexión y códigos. [Doctoral Dissertation]. Universidad de Cantabria; 2015. Available from: http://hdl.handle.net/10902/6542

Indian Institute of Science

9. Francis, Mathew C. Intersection Graphs Of Boxes And Cubes.

Degree: 2009, Indian Institute of Science

URL: http://hdl.handle.net/2005/1027

► A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such… (more)

▼ A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such that for u,v V(G), (u,v) E(G) ƒ (u) ƒ (v) ≠ . Interval graphs are thus the intersection graphs of closed intervals on the real line and unit interval graphs are the intersection graphs of unit length intervals on the real line. An interval on the real line can be generalized to a “kbox” in Rk.A kbox B =(R1,R2,...,Rk), where each Riis a closed interval on the real line, is defined to be the Cartesian product R1x R2x…x Rk. If each Ri is a unit length interval, we call B a k-cube. Thus, 1-boxes are just closed intervals on the real line whereas 2-boxes are axis-parallel rectangles in the plane. We study the intersection graphs of k-boxes and k-cubes. The parameter boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. Thus, interval graphs are the graphs with boxicity at most 1 and unit interval graphs are the graphs with cubicity at most 1. These parameters were introduced by F. S.Roberts in 1969. In some sense, the boxicity of a graph is a measure of how different a graph is from an interval graph and in a similar way, the cubicity is a measure of how different the graph is from a unit interval graph. We prove several upper bounds on the boxicity and cubicity of general as well as special classes of graphs in terms of various graph parameters such as the maximum degree, the number of vertices and the bandwidth. The following are some of the main results presented. 1. We show that for any graph G with maximum degree Δ , box(G)≤ Δ 22 . This result implies that bounded degree graphs have bounded boxicity no matter how large the graph might be. 2. It was shown in [18] that the boxicity of a graph on n vertices with maximum degree Δ is O(Δ ln n). But a similar bound does not hold for the average degree davof a graph. [18] gives graphs in which the boxicity is exponentially larger than davln n. We show that even though an O(davln n) upper bound for boxicity does not hold for all graphs, for almost all graphs, boxicity is O(davln n). 3. The ratio of the cubicity to boxicity of any graph shown in [15] when combined with the results on boxicity show that cub(G) is O(Δ ln 2 n) and O(2 ln n) for any graph G on n vertices and with maximum degree . By using a randomized construction, we prove the better upper bound cub(G) ≤ [4(Δ + 1) ln n.] 4. Two results relating the cubicity of a graph to its bandwidth b are presented. First, it is shown that cub(G) ≤ 12(Δ + 1)[ ln(2b)] + 1. Next, we derive the upper bound cub(G) ≤ b + 1. This bound is used to derive new upper bounds on the cubicity of special graph classes like circular arc graphs, cocomparability graphs and ATfree graphs in relation to the maximum degree. 5. The upper bound for cubicity in terms of the bandwidth gives an upper bound of Δ + 1 for the… Advisors/Committee Members: Chandran, L Sunil.

Subjects/Keywords: Computer Graphics; Boxicity (Graphs); Cubicity (Graphs); Interval Graphs; Halin Graphs; Planar Graphs; Intersection Graphs; Random Graphs; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Francis, M. C. (2009). Intersection Graphs Of Boxes And Cubes. (Thesis). Indian Institute of Science. Retrieved from http://hdl.handle.net/2005/1027

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Francis, Mathew C. “Intersection Graphs Of Boxes And Cubes.” 2009. Thesis, Indian Institute of Science. Accessed February 27, 2020. http://hdl.handle.net/2005/1027.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Francis, Mathew C. “Intersection Graphs Of Boxes And Cubes.” 2009. Web. 27 Feb 2020.

Vancouver:

Francis MC. Intersection Graphs Of Boxes And Cubes. [Internet] [Thesis]. Indian Institute of Science; 2009. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/2005/1027.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Francis MC. Intersection Graphs Of Boxes And Cubes. [Thesis]. Indian Institute of Science; 2009. Available from: http://hdl.handle.net/2005/1027

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Jawaharlal Nehru University

10. Krishna Reddy, Polepalli. Synchronization based on data flow graphs for distributed and replicated databases; -.

Degree: Computer Science, 1993, Jawaharlal Nehru University

URL: http://shodhganga.inflibnet.ac.in/handle/10603/16640

►

In this study, we present concurrency control algorithms based on data flow graphs for newlinedistributed and replicated databases. newlineGraphical representations such as token models and… (more)

▼

In this study, we present concurrency control algorithms based on data flow graphs for newlinedistributed and replicated databases. newlineGraphical representations such as token models and structure models are widely applied newlineto represent data flow programs. Data flow programs are represented by directed graphs called newlinedata flow graphs where nodes represent the operations to be performed and arcs represent newlinethe data dependencies between them. The scheduling of operations is constrained by the data newlinedependencies identified by the graph. So, data flow scheduling mechanism could execute newlineoperations based upon the dependency constraints defined by the data flow graph. In this newlineway, concurrency is achieved through graphs. newlineIn this study we explore t~~ use of data flow graphs to design concurrency control newlinealgorithms. Precedence graphs are often used to determine serializability, and wait-for-graphs newlineare often used to detect deadlocks. Among these, acyclic precedence graphs indicate newlineserializability, and acyclic wait-for-graphs imply freedom from deadlocks. The tools for newlineserializability theory, and transaction management coupled with data flow graphs will provide newlinesolutions that are more efficient than conventional concurrency control techniques, such as, newlinetwo-phase locking. In the same light, we apply data flow graphs for concurrency control for newlinedistributed, and replicated databases. newlineAt first, we propose a concurrency control algorithm based on data flow graphs for a newlinedistributed database system. The concurrency control approaches based on locking, require newlineadditional efforts in deadlock detection and its elimination. The deadlock resolution protocols newlineassociated with deadlock detection algorithms abort (restart) some transactions in the deadlock newlinecycle. The restarted transaction must release all its locks and send out the requests again. The newlinepossibility of a deadlock is also connected to existence of unpredictable delays and repeated newlinerestarts of transactions in a deadlock cycle.

Appendix p.134-143, Bibilography p.164, Abbrevations, Graphs

Advisors/Committee Members: Bharadwaj, K K, Bhalla, Subhash.

Subjects/Keywords: Computer Science; graphs; Replicated; databses; flow graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Krishna Reddy, P. (1993). Synchronization based on data flow graphs for distributed and replicated databases; -. (Thesis). Jawaharlal Nehru University. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/16640

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Krishna Reddy, Polepalli. “Synchronization based on data flow graphs for distributed and replicated databases; -.” 1993. Thesis, Jawaharlal Nehru University. Accessed February 27, 2020. http://shodhganga.inflibnet.ac.in/handle/10603/16640.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Krishna Reddy, Polepalli. “Synchronization based on data flow graphs for distributed and replicated databases; -.” 1993. Web. 27 Feb 2020.

Vancouver:

Krishna Reddy P. Synchronization based on data flow graphs for distributed and replicated databases; -. [Internet] [Thesis]. Jawaharlal Nehru University; 1993. [cited 2020 Feb 27]. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/16640.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Krishna Reddy P. Synchronization based on data flow graphs for distributed and replicated databases; -. [Thesis]. Jawaharlal Nehru University; 1993. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/16640

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Louisiana State University

11. Iverson, Perry K. Refining the characterization of projective graphs.

Degree: PhD, Applied Mathematics, 2013, Louisiana State University

URL: etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914

► Archdeacon showed that the class of graphs embeddable in the projective plane is characterized by a set of 35 excluded minors. Robertson, Seymour and Thomas… (more)

Subjects/Keywords: minors; excluded minors; projective graphs; graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Iverson, P. K. (2013). Refining the characterization of projective graphs. (Doctoral Dissertation). Louisiana State University. Retrieved from etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914

Chicago Manual of Style (16^th Edition):

Iverson, Perry K. “Refining the characterization of projective graphs.” 2013. Doctoral Dissertation, Louisiana State University. Accessed February 27, 2020. etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914.

MLA Handbook (7^th Edition):

Iverson, Perry K. “Refining the characterization of projective graphs.” 2013. Web. 27 Feb 2020.

Vancouver:

Iverson PK. Refining the characterization of projective graphs. [Internet] [Doctoral dissertation]. Louisiana State University; 2013. [cited 2020 Feb 27]. Available from: etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914.

Council of Science Editors:

Iverson PK. Refining the characterization of projective graphs. [Doctoral Dissertation]. Louisiana State University; 2013. Available from: etd-07072013-161459 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3914

Louisiana State University

12. Dziobiak, Stanislaw. Excluded-minor characterization of apex-outerplanar graphs.

Degree: PhD, Applied Mathematics, 2011, Louisiana State University

URL: etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102

► It is well known that the class of outerplanar graphs is minor-closed and can be characterized by two excluded minors: K₄ and K_2,3. The class… (more)

Subjects/Keywords: outerplanar graphs; excluded minors; minors; graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Dziobiak, S. (2011). Excluded-minor characterization of apex-outerplanar graphs. (Doctoral Dissertation). Louisiana State University. Retrieved from etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102

Chicago Manual of Style (16^th Edition):

Dziobiak, Stanislaw. “Excluded-minor characterization of apex-outerplanar graphs.” 2011. Doctoral Dissertation, Louisiana State University. Accessed February 27, 2020. etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102.

MLA Handbook (7^th Edition):

Dziobiak, Stanislaw. “Excluded-minor characterization of apex-outerplanar graphs.” 2011. Web. 27 Feb 2020.

Vancouver:

Dziobiak S. Excluded-minor characterization of apex-outerplanar graphs. [Internet] [Doctoral dissertation]. Louisiana State University; 2011. [cited 2020 Feb 27]. Available from: etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102.

Council of Science Editors:

Dziobiak S. Excluded-minor characterization of apex-outerplanar graphs. [Doctoral Dissertation]. Louisiana State University; 2011. Available from: etd-07062011-183918 ; https://digitalcommons.lsu.edu/gradschool_dissertations/3102

University of Newcastle

13. Feria Puron, Ramiro. Large interconnection networks with given degree and diameter.

Degree: PhD, 2015, University of Newcastle

URL: http://hdl.handle.net/1959.13/1295870

►

Research Doctorate - Doctor of Philosophy (PhD)

This thesis investigates and provides several answers for one of the most representative open problems in the design… (more)

▼

Research Doctorate - Doctor of Philosophy (PhD)

This thesis investigates and provides several answers for one of the most representative open problems in the design of interconnection networks. In the last few decades, the ability to design interconnection networks satisfying practical requirements and constraints has become a topic of major interest. In most circumstances, however, this has turned out to be a rather challenging task, leading to questions that have become the source of more than one interesting unsolved problem. One of these problems that has received significant attention deals with the design of networks as large as possible in terms of the number of nodes, given a limit on the number of connections attached to a node and a limit on the distance between any two nodes of the network. When translated to graph-theoretical terms this leads to the Degree/Diameter Problem, which asks for the largest number of vertices in a graph (and the graph itself) with a given maximum degree and diameter. The Degree/Diameter problem has been investigated since it was stated in 1964, yet is has endured as an open problem for more than fifty years now. A generous number of partial outcomes have been obtained to date, without narrowing the considerable gap remaining between the currently known upper and lower bounds for most degrees and diameters. The networks in question may be subject to further classification, such as being planar or bipartite, which restricts the Degree/Diameter Problem to the class of graphs under consideration. In this thesis we make substantial contributions to the Degree/Diameter Problem by providing improvements in the two traditional research directions: lowering the upper bounds for by proving the non-existence of graphs, and increasing the lower bounds by finding or giving constructions of ever larger graphs with given degree and diameter. The methodology used relies on a mixture of combinatorial approaches, graph compounding techniques, as well as algorithmic techniques and computer search. Our outcomes cover four of the most prominent classes of graphs studied: general graphs, bipartite graphs, circulant graphs, and graphs embeddable on surfaces. Among others, we obtain the following results: For the class of bipartite graphs, we use combinatorial approaches to improve the current upper bounds for more than two thirds of all possible combinations of degree and diameter. In a partially computer assisted proof, we prove that the largest known bipartite graph of degree 7 and diameter 3 is optimal. We also find by computer search a bipartite graph of degree 11 and diameter 3, thus improving the former lower bound by 4 vertices. ; For the class of general graphs, we use a similar strategy to improve the current upper bounds for more than one half of all possible combinations of degree and diameter. ; For the class of circulant graphs, we design and implement an efficient algorithm to find circulant graphs of small diameter. We find 15 largest known circulant graphs, with diameters ranging…

Advisors/Committee Members: University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science.

Subjects/Keywords: degree diameter problem; graphs; moore bound; bipartite graphs; circulant graphs; graphs on surfaces

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Feria Puron, R. (2015). Large interconnection networks with given degree and diameter. (Doctoral Dissertation). University of Newcastle. Retrieved from http://hdl.handle.net/1959.13/1295870

Chicago Manual of Style (16^th Edition):

Feria Puron, Ramiro. “Large interconnection networks with given degree and diameter.” 2015. Doctoral Dissertation, University of Newcastle. Accessed February 27, 2020. http://hdl.handle.net/1959.13/1295870.

MLA Handbook (7^th Edition):

Feria Puron, Ramiro. “Large interconnection networks with given degree and diameter.” 2015. Web. 27 Feb 2020.

Vancouver:

Feria Puron R. Large interconnection networks with given degree and diameter. [Internet] [Doctoral dissertation]. University of Newcastle; 2015. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/1959.13/1295870.

Council of Science Editors:

Feria Puron R. Large interconnection networks with given degree and diameter. [Doctoral Dissertation]. University of Newcastle; 2015. Available from: http://hdl.handle.net/1959.13/1295870

The Ohio State University

14. Poole, Daniel James. A Study of Random Hypergraphs and Directed Graphs.

Degree: PhD, Mathematics, 2014, The Ohio State University

URL: http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674

► We establish and describe the likely structure of random hypergraph and directed graph models, expanding upon classical results that pertain to the likely structure of… (more)

Subjects/Keywords: Mathematics; Random Graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Poole, D. J. (2014). A Study of Random Hypergraphs and Directed Graphs. (Doctoral Dissertation). The Ohio State University. Retrieved from http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674

Chicago Manual of Style (16^th Edition):

Poole, Daniel James. “A Study of Random Hypergraphs and Directed Graphs.” 2014. Doctoral Dissertation, The Ohio State University. Accessed February 27, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674.

MLA Handbook (7^th Edition):

Poole, Daniel James. “A Study of Random Hypergraphs and Directed Graphs.” 2014. Web. 27 Feb 2020.

Vancouver:

Poole DJ. A Study of Random Hypergraphs and Directed Graphs. [Internet] [Doctoral dissertation]. The Ohio State University; 2014. [cited 2020 Feb 27]. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674.

Council of Science Editors:

Poole DJ. A Study of Random Hypergraphs and Directed Graphs. [Doctoral Dissertation]. The Ohio State University; 2014. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674

University of Victoria

15. Hassanlou, Nasrin. Probabilistic graph summarization.

Degree: Dept. of Computer Science, 2013, University of Victoria

URL: http://hdl.handle.net/1828/4403

► We study group-summarization of probabilistic graphs that naturally arise in social networks, semistructured data, and other applications. Our proposed framework groups the nodes and edges… (more)

Subjects/Keywords: graphs; users; algorithms

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Hassanlou, N. (2013). Probabilistic graph summarization. (Masters Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/4403

Chicago Manual of Style (16^th Edition):

Hassanlou, Nasrin. “Probabilistic graph summarization.” 2013. Masters Thesis, University of Victoria. Accessed February 27, 2020. http://hdl.handle.net/1828/4403.

MLA Handbook (7^th Edition):

Hassanlou, Nasrin. “Probabilistic graph summarization.” 2013. Web. 27 Feb 2020.

Vancouver:

Hassanlou N. Probabilistic graph summarization. [Internet] [Masters thesis]. University of Victoria; 2013. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/1828/4403.

Council of Science Editors:

Hassanlou N. Probabilistic graph summarization. [Masters Thesis]. University of Victoria; 2013. Available from: http://hdl.handle.net/1828/4403

University of the Western Cape

16. Fadhal, Emad Alden Sir Alkhatim Abraham. Strong simplicity of groups and vertex - transitive graphs .

Degree: 2010, University of the Western Cape

URL: http://hdl.handle.net/11394/1430

► In the course of exploring various symmetries of vertex-transitive graphs, we introduce the concept of quasi-normal subgroups in groups. This is done since the symmetries… (more)

Subjects/Keywords: vertex-transitive graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Fadhal, E. A. S. A. A. (2010). Strong simplicity of groups and vertex - transitive graphs . (Thesis). University of the Western Cape. Retrieved from http://hdl.handle.net/11394/1430

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Fadhal, Emad Alden Sir Alkhatim Abraham. “Strong simplicity of groups and vertex - transitive graphs .” 2010. Thesis, University of the Western Cape. Accessed February 27, 2020. http://hdl.handle.net/11394/1430.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Fadhal, Emad Alden Sir Alkhatim Abraham. “Strong simplicity of groups and vertex - transitive graphs .” 2010. Web. 27 Feb 2020.

Vancouver:

Fadhal EASAA. Strong simplicity of groups and vertex - transitive graphs . [Internet] [Thesis]. University of the Western Cape; 2010. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/11394/1430.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Fadhal EASAA. Strong simplicity of groups and vertex - transitive graphs . [Thesis]. University of the Western Cape; 2010. Available from: http://hdl.handle.net/11394/1430

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

17. El Harabi, Rafika. Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes.

Degree: Docteur es, Automatique, Génie informatique, Traitement du Signal et Images, 2011, Université Lille I – Sciences et Technologies

URL: http://www.theses.fr/2011LIL10074

►

Le travail de thèse proposé concerne la conception intégrée des algorithmes de surveillance des processus chimiques à base de modèles bond graph. Cette recherche est… (more)

▼

Le travail de thèse proposé concerne la conception intégrée des algorithmes de surveillance des processus chimiques à base de modèles bond graph. Cette recherche est réalisée dans le cadre de la thématique «Bond graphs pour la supervision des procédés énergétiques» développée entre l’Université de Gabés (Tunisie) et l’Ecole Polytechnique Universitaire de Lille (France). Les processus chimiques sont des procédés polluants et à risque. Ils nécessitent alors pour la protection de l’environnement et du personnel des systèmes de surveillance en ligne pour la détection précoce et l’identification des défaillances. Un processus chimique est le siège de phénomènes de nature diverse : chimiques et ou biochimiques, thermo-fluidique, …. Leur modélisation nécessite alors une approche unifiée. L’outil bond graph par son caractère multidisciplinaire est bien adapté à cette tâche. D’autre part, cet outil peut aussi être utilisé pour la conception d’algorithmes de diagnostic grâce à ses propriétés comportementales, causales et structurelles et déterminer ainsi les conditions de surveillabilité structurelle des équipements pertinents sans calcul numérique. Les principales scientifiques contributions peuvent être résumées comme suit : (i) élaboration d’une bibliothèque de modèles Bond Graph de composants et phénomènes chimiques (ii) méthodologie de diagnostic à base de bond graphs pour la génération d’indicateurs de fautes sensibles à l’apparition des réactions secondaires sources de pollution et d’explosion, (iii) diagnostic robuste aux incertitudes paramétriques du modèle Bond Graphs couplés, (iv) informatisation des procédures d’analyse de surveillabilité d’une classe de procédés chimiques, (v) application à un procédé réel (installation d’estérification).

The proposed Ph.D. thesis deals with integrated design of bond graph model based for health monitoring of chemical processes. This research work is performed within the framework of the topic “Bond graphs for supervision of energetic processes" developed between the University of Gabés (Tunisia) and “Polytech’Lille”, the Engineering School within the University of Science and Technology of Lille. The chemical processes are polluting processes and with risk. They need, for staff safety and environmental protection, online surveillance for early detection and the identification of the failures. chemical processes occur phenomena of various nature: chemical and or biochemical, thermo-fluidic… Their modeling requires a unified approach. The Bond graph as a multidisciplinary tool is well suited to this task.Furthermore, this tool can be used also for the design of diagnosis algorithms thanks to its behavioral, causal and structural properties, and allows providing structural diagnosability conditions of the pertinent equipment without numerical calculation. The main scientific contributions of this research can be summarized as follows: (i)elaboration of a data base of dynamic bond graph models of components and chemical phenomena, (ii) methodology of bond graph model based…

Advisors/Committee Members: Ould Bouamama, Belkacem (thesis director), Abdelkrim, Mohamed Naceur (thesis director).

Subjects/Keywords: Bond Graphs; 629.895

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

El Harabi, R. (2011). Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes. (Doctoral Dissertation). Université Lille I – Sciences et Technologies. Retrieved from http://www.theses.fr/2011LIL10074

Chicago Manual of Style (16^th Edition):

El Harabi, Rafika. “Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes.” 2011. Doctoral Dissertation, Université Lille I – Sciences et Technologies. Accessed February 27, 2020. http://www.theses.fr/2011LIL10074.

MLA Handbook (7^th Edition):

El Harabi, Rafika. “Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes.” 2011. Web. 27 Feb 2020.

Vancouver:

El Harabi R. Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes. [Internet] [Doctoral dissertation]. Université Lille I – Sciences et Technologies; 2011. [cited 2020 Feb 27]. Available from: http://www.theses.fr/2011LIL10074.

Council of Science Editors:

El Harabi R. Supervision des processus chimiques à base de modèles Bond Graphs : Bond Graph Model Based for Supervision of Chemical Processes. [Doctoral Dissertation]. Université Lille I – Sciences et Technologies; 2011. Available from: http://www.theses.fr/2011LIL10074

University of Waterloo

18. Lato, Sabrina. Quantum Walks on Oriented Graphs.

Degree: 2019, University of Waterloo

URL: http://hdl.handle.net/10012/14338

► This thesis extends results about periodicity and perfect state transfer to oriented graphs. We prove that if a vertex a is periodic, then elements of… (more)

Subjects/Keywords: quantum walks; graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Lato, S. (2019). Quantum Walks on Oriented Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/14338

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Lato, Sabrina. “Quantum Walks on Oriented Graphs.” 2019. Thesis, University of Waterloo. Accessed February 27, 2020. http://hdl.handle.net/10012/14338.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Lato, Sabrina. “Quantum Walks on Oriented Graphs.” 2019. Web. 27 Feb 2020.

Vancouver:

Lato S. Quantum Walks on Oriented Graphs. [Internet] [Thesis]. University of Waterloo; 2019. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/10012/14338.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Lato S. Quantum Walks on Oriented Graphs. [Thesis]. University of Waterloo; 2019. Available from: http://hdl.handle.net/10012/14338

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Victoria University of Wellington

19. Snook, Michael. Matroids, Complexity and Computation.

Degree: 2013, Victoria University of Wellington

URL: http://hdl.handle.net/10063/2885

► The node deletion problem on graphs is: given a graph and integer k, can we delete no more than k vertices to obtain a graph… (more)

Subjects/Keywords: Graphs; Computation; Complexity

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Snook, M. (2013). Matroids, Complexity and Computation. (Doctoral Dissertation). Victoria University of Wellington. Retrieved from http://hdl.handle.net/10063/2885

Chicago Manual of Style (16^th Edition):

Snook, Michael. “Matroids, Complexity and Computation.” 2013. Doctoral Dissertation, Victoria University of Wellington. Accessed February 27, 2020. http://hdl.handle.net/10063/2885.

MLA Handbook (7^th Edition):

Snook, Michael. “Matroids, Complexity and Computation.” 2013. Web. 27 Feb 2020.

Vancouver:

Snook M. Matroids, Complexity and Computation. [Internet] [Doctoral dissertation]. Victoria University of Wellington; 2013. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/10063/2885.

Council of Science Editors:

Snook M. Matroids, Complexity and Computation. [Doctoral Dissertation]. Victoria University of Wellington; 2013. Available from: http://hdl.handle.net/10063/2885

University of Victoria

20. Neilson, Linda. Broadcast independence in graphs.

Degree: Department of Mathematics and Statistics, 2019, University of Victoria

URL: http://hdl.handle.net/1828/11084

► The usual graph parameters related to independent and dominating sets can be adapted to broadcasts on graphs. We examine some possible definitions for an inde-… (more)

Subjects/Keywords: Broadcasts; Graphs; Independence

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Neilson, L. (2019). Broadcast independence in graphs. (Thesis). University of Victoria. Retrieved from http://hdl.handle.net/1828/11084

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Neilson, Linda. “Broadcast independence in graphs.” 2019. Thesis, University of Victoria. Accessed February 27, 2020. http://hdl.handle.net/1828/11084.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Neilson, Linda. “Broadcast independence in graphs.” 2019. Web. 27 Feb 2020.

Vancouver:

Neilson L. Broadcast independence in graphs. [Internet] [Thesis]. University of Victoria; 2019. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/1828/11084.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Neilson L. Broadcast independence in graphs. [Thesis]. University of Victoria; 2019. Available from: http://hdl.handle.net/1828/11084

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Kansas

21. Adams, Kevin Daniel. On Kernels, β-graphs, and β-graph Sequences of Digraphs.

Degree: MA, Mathematics, 2015, University of Kansas

URL: http://hdl.handle.net/1808/19005

► We begin by investigating some conditions determining the existence of kernels in various classes of directed graphs, most notably in oriented trees, grid graphs, and… (more)

Subjects/Keywords: Mathematics; Absorbant Sets; Directed Graphs; Dominating Sets; β-graphs; 𝛾-graphs

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Adams, K. D. (2015). On Kernels, β-graphs, and β-graph Sequences of Digraphs. (Masters Thesis). University of Kansas. Retrieved from http://hdl.handle.net/1808/19005

Chicago Manual of Style (16^th Edition):

Adams, Kevin Daniel. “On Kernels, β-graphs, and β-graph Sequences of Digraphs.” 2015. Masters Thesis, University of Kansas. Accessed February 27, 2020. http://hdl.handle.net/1808/19005.

MLA Handbook (7^th Edition):

Adams, Kevin Daniel. “On Kernels, β-graphs, and β-graph Sequences of Digraphs.” 2015. Web. 27 Feb 2020.

Vancouver:

Adams KD. On Kernels, β-graphs, and β-graph Sequences of Digraphs. [Internet] [Masters thesis]. University of Kansas; 2015. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/1808/19005.

Council of Science Editors:

Adams KD. On Kernels, β-graphs, and β-graph Sequences of Digraphs. [Masters Thesis]. University of Kansas; 2015. Available from: http://hdl.handle.net/1808/19005

Western Michigan University

22. Byers, Alexis D. Graceful Colorings and Connection in Graphs.

Degree: PhD, Mathematics, 2018, Western Michigan University

URL: https://scholarworks.wmich.edu/dissertations/3308

► For a graph G of size m, a graceful labeling of G is an injective function f : V (G) → {0, 1, .… (more)

Subjects/Keywords: Graphs; coloring in graphs; connections in graphs; mathematics; Mathematics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Byers, A. D. (2018). Graceful Colorings and Connection in Graphs. (Doctoral Dissertation). Western Michigan University. Retrieved from https://scholarworks.wmich.edu/dissertations/3308

Chicago Manual of Style (16^th Edition):

Byers, Alexis D. “Graceful Colorings and Connection in Graphs.” 2018. Doctoral Dissertation, Western Michigan University. Accessed February 27, 2020. https://scholarworks.wmich.edu/dissertations/3308.

MLA Handbook (7^th Edition):

Byers, Alexis D. “Graceful Colorings and Connection in Graphs.” 2018. Web. 27 Feb 2020.

Vancouver:

Byers AD. Graceful Colorings and Connection in Graphs. [Internet] [Doctoral dissertation]. Western Michigan University; 2018. [cited 2020 Feb 27]. Available from: https://scholarworks.wmich.edu/dissertations/3308.

Council of Science Editors:

Byers AD. Graceful Colorings and Connection in Graphs. [Doctoral Dissertation]. Western Michigan University; 2018. Available from: https://scholarworks.wmich.edu/dissertations/3308

23. Skrepetos, Dimitrios. Shortest Paths in Geometric Intersection Graphs.

Degree: 2018, University of Waterloo

URL: http://hdl.handle.net/10012/13454

► This thesis studies shortest paths in geometric intersection graphs, which can model, among others, ad-hoc communication and transportation networks. First, we consider two classical problems… (more)

▼ This thesis studies shortest paths in geometric intersection graphs, which can model, among others, ad-hoc communication and transportation networks. First, we consider two classical problems in the field of algorithms, namely Single-Source Shortest Paths (SSSP) and All-Pairs Shortest Paths (APSP). In SSSP we want to compute the shortest paths from one vertex of a graph to all other vertices, while in APSP we aim to find the shortest path between every pair of vertices. Although there is a vast literature for these problems in many graph classes, the case of geometric intersection graphs has been only partially addressed. In unweighted unit-disk graphs, we show that we can solve SSSP in linear time, after presorting the disk centers with respect to their coordinates. Furthermore, we give the first (slightly) subquadratic-time APSP algorithm by using our new SSSP result, bit tricks, and a shifted-grid-based decomposition technique. In unweighted, undirected geometric intersection graphs, we present a simple and general technique that reduces APSP to static, offline intersection detection. Consequently, we give fast APSP algorithms for intersection graphs of arbitrary disks, axis-aligned line segments, arbitrary line segments, d-dimensional axis-aligned boxes, and d-dimensional axis-aligned unit hypercubes. We also provide a near-linear-time SSSP algorithm for intersection graphs of axis-aligned line segments by a reduction to dynamic orthogonal point location. Then, we study two problems that have received considerable attention lately. The first is that of computing the diameter of a graph, i.e., the longest shortest-path distance between any two vertices. In the second, we want to preprocess a graph into a data structure, called distance oracle, such that the shortest path (or its length) between any two query vertices can be found quickly. Since these problems are often too costly to solve exactly, we study their approximate versions. Following a long line of research, we employ Voronoi diagrams to compute a (1+epsilon)-approximation of the diameter of an undirected, non-negatively-weighted planar graph in time near linear in the input size and polynomial in 1/epsilon. The previously best solution had exponential dependency on the latter. Using similar techniques, we can also construct the first (1+epsilon)-approximate distance oracles with similar preprocessing time and space and only O(log(1/ε)) query time. In weighted unit-disk graphs, we present the first near-linear-time (1+epsilon)-approximation algorithm for the diameter and for other related problems, such as the radius and the bichromatic closest pair. To do so, we combine techniques from computational geometry and planar graphs, namely well-separated pair decompositions and shortest-path separators. We also show how to extend our approach to obtain O(1)-query-time (1+epsilon)-approximate distance oracles with near linear preprocessing time and space. Then, we apply these oracles, along with additional ideas, to build a data…

Subjects/Keywords: shortest paths; unit-disk graphs; planar graphs; geometric intersection graphs; diameter

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Skrepetos, D. (2018). Shortest Paths in Geometric Intersection Graphs. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/13454

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Skrepetos, Dimitrios. “Shortest Paths in Geometric Intersection Graphs.” 2018. Thesis, University of Waterloo. Accessed February 27, 2020. http://hdl.handle.net/10012/13454.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Skrepetos, Dimitrios. “Shortest Paths in Geometric Intersection Graphs.” 2018. Web. 27 Feb 2020.

Vancouver:

Skrepetos D. Shortest Paths in Geometric Intersection Graphs. [Internet] [Thesis]. University of Waterloo; 2018. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/10012/13454.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Skrepetos D. Shortest Paths in Geometric Intersection Graphs. [Thesis]. University of Waterloo; 2018. Available from: http://hdl.handle.net/10012/13454

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Indian Institute of Science

24. Mathew, Rogers. Boxicity And Cubicity : A Study On Special Classes Of Graphs.

Degree: 2012, Indian Institute of Science

URL: http://hdl.handle.net/2005/2320

► Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping… (more)

▼ Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1. The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable. Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work. 1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor. 2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation. 3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ). 4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average… Advisors/Committee Members: Chandran, L Sunil.

Subjects/Keywords: Graphs; Boxicity; Leaf Powers; Random Grpahs; Line Graphs; Chordal Bipartite Graphs; Random Graphs; k-chordal Graphs; Crossing Number; Cubicity; Geometry

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Mathew, R. (2012). Boxicity And Cubicity : A Study On Special Classes Of Graphs. (Thesis). Indian Institute of Science. Retrieved from http://hdl.handle.net/2005/2320

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Mathew, Rogers. “Boxicity And Cubicity : A Study On Special Classes Of Graphs.” 2012. Thesis, Indian Institute of Science. Accessed February 27, 2020. http://hdl.handle.net/2005/2320.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Mathew, Rogers. “Boxicity And Cubicity : A Study On Special Classes Of Graphs.” 2012. Web. 27 Feb 2020.

Vancouver:

Mathew R. Boxicity And Cubicity : A Study On Special Classes Of Graphs. [Internet] [Thesis]. Indian Institute of Science; 2012. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/2005/2320.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Mathew R. Boxicity And Cubicity : A Study On Special Classes Of Graphs. [Thesis]. Indian Institute of Science; 2012. Available from: http://hdl.handle.net/2005/2320

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Indian Institute of Science

25. Mathew, Rogers. Boxicity And Cubicity : A Study On Special Classes Of Graphs.

Degree: 2012, Indian Institute of Science

URL: http://etd.iisc.ernet.in/handle/2005/2320 ; http://etd.ncsi.iisc.ernet.in/abstracts/2983/G25263-Abs.pdf

► Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping… (more)

▼ Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1. The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable. Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work. 1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor. 2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation. 3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ). 4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average… Advisors/Committee Members: Chandran, L Sunil.

Subjects/Keywords: Graphs; Boxicity; Leaf Powers; Random Grpahs; Line Graphs; Chordal Bipartite Graphs; Random Graphs; k-chordal Graphs; Crossing Number; Cubicity; Geometry

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Mathew, R. (2012). Boxicity And Cubicity : A Study On Special Classes Of Graphs. (Thesis). Indian Institute of Science. Retrieved from http://etd.iisc.ernet.in/handle/2005/2320 ; http://etd.ncsi.iisc.ernet.in/abstracts/2983/G25263-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Mathew, Rogers. “Boxicity And Cubicity : A Study On Special Classes Of Graphs.” 2012. Thesis, Indian Institute of Science. Accessed February 27, 2020. http://etd.iisc.ernet.in/handle/2005/2320 ; http://etd.ncsi.iisc.ernet.in/abstracts/2983/G25263-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Mathew, Rogers. “Boxicity And Cubicity : A Study On Special Classes Of Graphs.” 2012. Web. 27 Feb 2020.

Vancouver:

Mathew R. Boxicity And Cubicity : A Study On Special Classes Of Graphs. [Internet] [Thesis]. Indian Institute of Science; 2012. [cited 2020 Feb 27]. Available from: http://etd.iisc.ernet.in/handle/2005/2320 ; http://etd.ncsi.iisc.ernet.in/abstracts/2983/G25263-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Mathew R. Boxicity And Cubicity : A Study On Special Classes Of Graphs. [Thesis]. Indian Institute of Science; 2012. Available from: http://etd.iisc.ernet.in/handle/2005/2320 ; http://etd.ncsi.iisc.ernet.in/abstracts/2983/G25263-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Tennessee – Knoxville

26. McClurkin, Grace Elizabeth. Generalizations and Variations of the Zero-Divisor Graph.

Degree: 2017, University of Tennessee – Knoxville

URL: https://trace.tennessee.edu/utk_graddiss/4701

► We explore generalizations and variations of the zero-divisor graph on commutative rings with identity. A zero-divisor graph is a graph whose vertex set is the… (more)

Subjects/Keywords: Commutative Ring Theory; Zero-Divisor Graphs; Congruence-Based Zero-Divisor Graphs; Annihilator Graphs; Extended Zero-Divisor Graphs; Compressed Graphs; Algebra

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

McClurkin, G. E. (2017). Generalizations and Variations of the Zero-Divisor Graph. (Doctoral Dissertation). University of Tennessee – Knoxville. Retrieved from https://trace.tennessee.edu/utk_graddiss/4701

Chicago Manual of Style (16^th Edition):

McClurkin, Grace Elizabeth. “Generalizations and Variations of the Zero-Divisor Graph.” 2017. Doctoral Dissertation, University of Tennessee – Knoxville. Accessed February 27, 2020. https://trace.tennessee.edu/utk_graddiss/4701.

MLA Handbook (7^th Edition):

McClurkin, Grace Elizabeth. “Generalizations and Variations of the Zero-Divisor Graph.” 2017. Web. 27 Feb 2020.

Vancouver:

McClurkin GE. Generalizations and Variations of the Zero-Divisor Graph. [Internet] [Doctoral dissertation]. University of Tennessee – Knoxville; 2017. [cited 2020 Feb 27]. Available from: https://trace.tennessee.edu/utk_graddiss/4701.

Council of Science Editors:

McClurkin GE. Generalizations and Variations of the Zero-Divisor Graph. [Doctoral Dissertation]. University of Tennessee – Knoxville; 2017. Available from: https://trace.tennessee.edu/utk_graddiss/4701

Indian Institute of Science

27. Khopkar, Abhijeet. Computational And Combinatorial Problems On Some Geometric Proximity Graphs.

Degree: 2013, Indian Institute of Science

URL: http://etd.iisc.ernet.in/handle/2005/2622 ; http://etd.ncsi.iisc.ernet.in/abstracts/3401/G26269-Abs.pdf

► In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied… (more)

▼ In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied geometric proximity structures. These graphs have been extensively studied for their applications in wireless networks. Motivated by the applications in localized wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Locally Gabriel Graphs(LGGs) were proposed. A geometric graph G=(V,E)is called a Locally Gabriel Graph if for every( u,v) ϵ E the disk with uv as diameter does not contain any neighbor of u or v in G. Thus, two edges (u, v) and(u, w)where u,v,w ϵ V conflict with each other if ∠uwv ≥ or ∠uvw≥π and cannot co-exist in an LGG. We propose another generalization of LGGs called Generalized locally Gabriel Graphs(GLGGs)in the context when certain edges are forbidden in the graph. For a given geometric graph G=(V,E), we define G′=(V,E′) as GLGG if G′is an LGG and E′⊆E. Unlike a Gabriel Graph ,there is no unique LGG or GLGG for a given point set because no edge is necessarily included or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. While Gabriel graphs are planar graphs, there exist LGGs with super linear number of edges. Also, there exist point sets where a Gabriel graph has dilation of Ω(√n)and there exist LGGs on the same point sets with dilation O(1). We study these graphs for various parameters like edge complexity(the maximum number of edges in these graphs),size of an independent set and dilation. We show that computing an edge maximum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with minimum dilation is NP-hard. Then, we give an algorithm to verify whether a given geometric graph G=(V,E)is an LGG with running time O(ElogV+ V). We show that any LGG on n vertices has an independent set of size Ω(√nlogn). We show that there exists point sets with n points such that any LGG on it has dilation Ω(√n) that matches with the known upper bound. Then, we study some greedy heuristics to compute LGGs with experimental evaluation. Experimental evaluations for the points on a uniform grid and random point sets suggest that there exist LGGs with super-linear number of edges along with an independent set of near-linear size. Unit distance graphs(UDGs) are well studied geometric graphs. In this graph, an edge exists between two points if and only if the Euclidean distance between the points is unity. UDGs have been studied extensively for various properties most notably for their edge complexity and chromatic number. These graphs have also been studied for various special point sets most notably the case when the points are in convex position. Note that the UDGs form a sub class of the LGGs. UDGs/LGGs on convex point sets have O(nlogn) edges. The best known lower bound on the edge complexity of these graphs is 2n−7 when all the points are in convex position. A bipartite graph… Advisors/Committee Members: Govindrajan, Sathish.

Subjects/Keywords: Geometric Proximity Graphs; Computational Geometry; Geometric Graphs; Gabriel Graphs; Locally Gabriel Graphs; Unit Distance Graphs; Ordered Bipartite Graphs; Convex Point Sets; Combinatorial Geometry; Locally Gabriel Geometric Graphs; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Khopkar, A. (2013). Computational And Combinatorial Problems On Some Geometric Proximity Graphs. (Thesis). Indian Institute of Science. Retrieved from http://etd.iisc.ernet.in/handle/2005/2622 ; http://etd.ncsi.iisc.ernet.in/abstracts/3401/G26269-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Khopkar, Abhijeet. “Computational And Combinatorial Problems On Some Geometric Proximity Graphs.” 2013. Thesis, Indian Institute of Science. Accessed February 27, 2020. http://etd.iisc.ernet.in/handle/2005/2622 ; http://etd.ncsi.iisc.ernet.in/abstracts/3401/G26269-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Khopkar, Abhijeet. “Computational And Combinatorial Problems On Some Geometric Proximity Graphs.” 2013. Web. 27 Feb 2020.

Vancouver:

Khopkar A. Computational And Combinatorial Problems On Some Geometric Proximity Graphs. [Internet] [Thesis]. Indian Institute of Science; 2013. [cited 2020 Feb 27]. Available from: http://etd.iisc.ernet.in/handle/2005/2622 ; http://etd.ncsi.iisc.ernet.in/abstracts/3401/G26269-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Khopkar A. Computational And Combinatorial Problems On Some Geometric Proximity Graphs. [Thesis]. Indian Institute of Science; 2013. Available from: http://etd.iisc.ernet.in/handle/2005/2622 ; http://etd.ncsi.iisc.ernet.in/abstracts/3401/G26269-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Indian Institute of Science

28. Khopkar, Abhijeet. Computational And Combinatorial Problems On Some Geometric Proximity Graphs.

Degree: 2013, Indian Institute of Science

URL: http://hdl.handle.net/2005/2622

► In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied… (more)

▼ In this thesis, we focus on the study of computational and combinatorial problems on various geometric proximity graphs. Delaunay and Gabriel graphs are widely studied geometric proximity structures. These graphs have been extensively studied for their applications in wireless networks. Motivated by the applications in localized wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Locally Gabriel Graphs(LGGs) were proposed. A geometric graph G=(V,E)is called a Locally Gabriel Graph if for every( u,v) ϵ E the disk with uv as diameter does not contain any neighbor of u or v in G. Thus, two edges (u, v) and(u, w)where u,v,w ϵ V conflict with each other if ∠uwv ≥ or ∠uvw≥π and cannot co-exist in an LGG. We propose another generalization of LGGs called Generalized locally Gabriel Graphs(GLGGs)in the context when certain edges are forbidden in the graph. For a given geometric graph G=(V,E), we define G′=(V,E′) as GLGG if G′is an LGG and E′⊆E. Unlike a Gabriel Graph ,there is no unique LGG or GLGG for a given point set because no edge is necessarily included or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. While Gabriel graphs are planar graphs, there exist LGGs with super linear number of edges. Also, there exist point sets where a Gabriel graph has dilation of Ω(√n)and there exist LGGs on the same point sets with dilation O(1). We study these graphs for various parameters like edge complexity(the maximum number of edges in these graphs),size of an independent set and dilation. We show that computing an edge maximum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with minimum dilation is NP-hard. Then, we give an algorithm to verify whether a given geometric graph G=(V,E)is an LGG with running time O(ElogV+ V). We show that any LGG on n vertices has an independent set of size Ω(√nlogn). We show that there exists point sets with n points such that any LGG on it has dilation Ω(√n) that matches with the known upper bound. Then, we study some greedy heuristics to compute LGGs with experimental evaluation. Experimental evaluations for the points on a uniform grid and random point sets suggest that there exist LGGs with super-linear number of edges along with an independent set of near-linear size. Unit distance graphs(UDGs) are well studied geometric graphs. In this graph, an edge exists between two points if and only if the Euclidean distance between the points is unity. UDGs have been studied extensively for various properties most notably for their edge complexity and chromatic number. These graphs have also been studied for various special point sets most notably the case when the points are in convex position. Note that the UDGs form a sub class of the LGGs. UDGs/LGGs on convex point sets have O(nlogn) edges. The best known lower bound on the edge complexity of these graphs is 2n−7 when all the points are in convex position. A bipartite graph… Advisors/Committee Members: Govindrajan, Sathish.

Subjects/Keywords: Geometric Proximity Graphs; Computational Geometry; Geometric Graphs; Gabriel Graphs; Locally Gabriel Graphs; Unit Distance Graphs; Ordered Bipartite Graphs; Convex Point Sets; Combinatorial Geometry; Locally Gabriel Geometric Graphs; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Khopkar, A. (2013). Computational And Combinatorial Problems On Some Geometric Proximity Graphs. (Thesis). Indian Institute of Science. Retrieved from http://hdl.handle.net/2005/2622

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Khopkar, Abhijeet. “Computational And Combinatorial Problems On Some Geometric Proximity Graphs.” 2013. Thesis, Indian Institute of Science. Accessed February 27, 2020. http://hdl.handle.net/2005/2622.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Khopkar, Abhijeet. “Computational And Combinatorial Problems On Some Geometric Proximity Graphs.” 2013. Web. 27 Feb 2020.

Vancouver:

Khopkar A. Computational And Combinatorial Problems On Some Geometric Proximity Graphs. [Internet] [Thesis]. Indian Institute of Science; 2013. [cited 2020 Feb 27]. Available from: http://hdl.handle.net/2005/2622.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Khopkar A. Computational And Combinatorial Problems On Some Geometric Proximity Graphs. [Thesis]. Indian Institute of Science; 2013. Available from: http://hdl.handle.net/2005/2622

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Indian Institute of Science

29. Rajendraprasad, Deepak. Rainbow Colouring and Some Dimensional Problems in Graph Theory.

Degree: 2013, Indian Institute of Science

URL: http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf

► This thesis touches three diﬀerent topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is… (more)

Subjects/Keywords: Graph Theory; Rainbow Coloring - Graphs; Product Dimension - Graphs; Boxicity; Cubicity; Hypergraphs; Product Graphs; Forests Graphs; Treewidth Graphs; Tree (Graph Theory); Split Graphs; Threshold Graphs; Graph - Coloring; Rainbow Connection; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Rajendraprasad, D. (2013). Rainbow Colouring and Some Dimensional Problems in Graph Theory. (Thesis). Indian Institute of Science. Retrieved from http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Rajendraprasad, Deepak. “Rainbow Colouring and Some Dimensional Problems in Graph Theory.” 2013. Thesis, Indian Institute of Science. Accessed February 27, 2020. http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Rajendraprasad, Deepak. “Rainbow Colouring and Some Dimensional Problems in Graph Theory.” 2013. Web. 27 Feb 2020.

Vancouver:

Rajendraprasad D. Rainbow Colouring and Some Dimensional Problems in Graph Theory. [Internet] [Thesis]. Indian Institute of Science; 2013. [cited 2020 Feb 27]. Available from: http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Rajendraprasad D. Rainbow Colouring and Some Dimensional Problems in Graph Theory. [Thesis]. Indian Institute of Science; 2013. Available from: http://etd.iisc.ernet.in/2005/3336 ; http://etd.iisc.ernet.in/abstracts/4201/G25730-Abs.pdf

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Temple University

30. Gidelew, Getnet Abebe. Topics in Harmonic Analysis on Combinatorial Graphs.

Degree: PhD, 2014, Temple University

URL: http://digital.library.temple.edu/u?/p245801coll10,262601

►

Mathematics

In recent years harmonic analysis on combinatorial graphs has attracted considerable attention. The interest is stimulated in part by multiple existing and potential applications… (more)

Subjects/Keywords: Mathematics;

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Gidelew, G. A. (2014). Topics in Harmonic Analysis on Combinatorial Graphs. (Doctoral Dissertation). Temple University. Retrieved from http://digital.library.temple.edu/u?/p245801coll10,262601

Chicago Manual of Style (16^th Edition):

Gidelew, Getnet Abebe. “Topics in Harmonic Analysis on Combinatorial Graphs.” 2014. Doctoral Dissertation, Temple University. Accessed February 27, 2020. http://digital.library.temple.edu/u?/p245801coll10,262601.

MLA Handbook (7^th Edition):

Gidelew, Getnet Abebe. “Topics in Harmonic Analysis on Combinatorial Graphs.” 2014. Web. 27 Feb 2020.

Vancouver:

Gidelew GA. Topics in Harmonic Analysis on Combinatorial Graphs. [Internet] [Doctoral dissertation]. Temple University; 2014. [cited 2020 Feb 27]. Available from: http://digital.library.temple.edu/u?/p245801coll10,262601.

Council of Science Editors:

Gidelew GA. Topics in Harmonic Analysis on Combinatorial Graphs. [Doctoral Dissertation]. Temple University; 2014. Available from: http://digital.library.temple.edu/u?/p245801coll10,262601

Open Access Theses and Dissertations