Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

Sorted by: relevance · author · university · dateNew search

You searched for subject:(Star decomposition). Showing records 1 – 3 of 3 total matches.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Waikato

1. Lim, Jin Sean. Star Decompositions of Bipartite Graphs .

Degree: 2015, University of Waikato

In Chapter 1, we will introduce the definitions and the notations used throughout this thesis. We will also survey some prior research pertaining to graph decompositions, with special emphasis on star-decompositions and decompositions of bipartite graphs. Here we will also introduce some basic algorithms and lemmas that are used in this thesis. In Chapter 2, we will focus primarily on decomposition of complete bipartite graphs. We will also cover the necessary and sufficient conditions for the decomposition of complete bipartite graphs minus a 1-factor, also known as crown graphs and show that all complete bipartite graphs and crown graphs have a decomposition into stars when certain necessary conditions for the decomposition are met. This is an extension of the results given in "On claw-decomposition of complete graphs and complete bigraphs" by Yamamoto, et. al. We will propose a construction for the decomposition of the graphs. In Chapter 3, we focus on the decomposition of complete equipartite tripartite graphs. This result is similar to the results of "On Claw-decomposition of complete multipartite graphs" by Ushio and Yamamoto. Our proof is again by construction and we propose how it might extend to equipartite multipartite graphs. We will also discuss the 3-star decomposition of complete tripartite graphs. In Chapter 4 , we will discuss the star decomposition of 4-regular bipartite graphs, with particular emphasis on the decomposition of 4-regular bipartite graphs into 3-stars. We will propose methods to extend our strategies to model the problem as an optimization problem. We will also look into the probabilistic method discussed in "Tree decomposition of Graphs" by Yuster and how we might modify the results of this paper to star decompositions of bipartite graphs. In Chapter 5, we summarize the findings in this thesis, and discuss the future work and research in star decompositions of bipartite and multipartite graphs. Advisors/Committee Members: Cavenagh, Nicholas J (advisor).

Subjects/Keywords: Graph Decomposition; Bipartite; Star Graphs; Multipartite

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Lim, J. S. (2015). Star Decompositions of Bipartite Graphs . (Masters Thesis). University of Waikato. Retrieved from http://hdl.handle.net/10289/9303

Chicago Manual of Style (16th Edition):

Lim, Jin Sean. “Star Decompositions of Bipartite Graphs .” 2015. Masters Thesis, University of Waikato. Accessed July 14, 2020. http://hdl.handle.net/10289/9303.

MLA Handbook (7th Edition):

Lim, Jin Sean. “Star Decompositions of Bipartite Graphs .” 2015. Web. 14 Jul 2020.

Vancouver:

Lim JS. Star Decompositions of Bipartite Graphs . [Internet] [Masters thesis]. University of Waikato; 2015. [cited 2020 Jul 14]. Available from: http://hdl.handle.net/10289/9303.

Council of Science Editors:

Lim JS. Star Decompositions of Bipartite Graphs . [Masters Thesis]. University of Waikato; 2015. Available from: http://hdl.handle.net/10289/9303

2. Neggazi, Brahim. Self-stabilizing algorithms for graph parameters : Algorithmes auto-stabilisants pour des paramètres de graphes.

Degree: Docteur es, Informatique, 2015, Université Claude Bernard – Lyon I

Le concept d'auto-stabilisation a été introduit par Dijkstra en 1973. Un système distribué est auto-stabilisant s'il peut démarrer de n'importe quelle configuration initiale et retrouver une configuration légitime en un temps fini par lui-même et sans aucune intervention extérieure. La convergence est également garantie lorsque le système est affecté par des fautes transitoires, ce qui en fait une approche élégante, non masquante, pour la tolérance aux pannes. L'auto-stabilisation a été étudiée dans divers domaines des systèmes distribués tels que les problèmes de synchronisation de l'horloge, de la communication et les protocoles de routage. Vu l'importance des paramètres de graphes notamment pour l'organisation et l'optimisation des communications dans les réseaux et les systèmes distribués, plusieurs algorithmes auto-stabilisants pour des paramètres de graphe ont été proposés dans la littérature, tels que les algorithmes autostabilisants permettant de trouver les ensembles dominants minimaux, coloration des graphes, couplage maximal et arbres de recouvrement. Dans cette perspective, nous proposons, dans cette thèse, des algorithmes distribués et autostabilisants pour certains problèmes de graphes bien connus, en particulier pour les décompositions de graphes et les ensembles dominants qui n'ont pas encore été abordés avec le concept de l'autostabilisation. Les quatre problèmes majeurs considérés dans cette thèse sont: partitionnement en triangles, décomposition en p-étoiles, Monitoring des arêtes, fort ensemble dominant et indépendant. Ainsi, le point commun entre ces problèmes, est qu'ils sont tous considérés comme des variantes des problèmes de domination et de couplage dans les graphes et leur traitement se fait d'une manière auto-stabilisante

The concept of self-stabilization was first introduced by Dijkstra in 1973. A distributed system is self-stabilizing if it can start from any possible configuration and converges to a desired configuration in finite time by itself without using any external intervention. Convergence is also guaranteed when the system is affected by transient faults. This makes self-stabilization an effective approach for non-masking fault-tolerance. The self-stabilization was studied in various fields in distributed systems such as the problems of clock synchronization, communication and routing protocols. Given the importance of graph parameters, especially for organization and communication of networks and distributed systems, several self-stabilizing algorithms for classic graph parameters have been developed in this direction, such as self-stabilizing algorithms for finding minimal dominating sets, coloring, maximal matching, spanning tree and so on. Thence, we propose in this thesis, distributed and self-stabilizing algorithms to some wellknown graphs problems, particularly for graph decompositions and dominating sets problems that have not yet been addressed in a view of self-stabilization. The four major problems considered in this thesis are: the partitioning into triangles,…

Advisors/Committee Members: Kheddouci, Hamamache (thesis director), Haddad, Mohammed (thesis director).

Subjects/Keywords: Algorithmes autostabilisants; Partitionnement en triangles; Décomposition en p-étoiles; Systèmes distribués; Problème du monitoring des arêtes; Fort ensemble dominant; Tolérance aux pannes; Self-stabilizing algorithms; Partitioning into triangles; P-star decomposition; Distributed system; Edge monitoring problem; Strong dominating set; Faulttolerance; 004

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Neggazi, B. (2015). Self-stabilizing algorithms for graph parameters : Algorithmes auto-stabilisants pour des paramètres de graphes. (Doctoral Dissertation). Université Claude Bernard – Lyon I. Retrieved from http://www.theses.fr/2015LYO10041

Chicago Manual of Style (16th Edition):

Neggazi, Brahim. “Self-stabilizing algorithms for graph parameters : Algorithmes auto-stabilisants pour des paramètres de graphes.” 2015. Doctoral Dissertation, Université Claude Bernard – Lyon I. Accessed July 14, 2020. http://www.theses.fr/2015LYO10041.

MLA Handbook (7th Edition):

Neggazi, Brahim. “Self-stabilizing algorithms for graph parameters : Algorithmes auto-stabilisants pour des paramètres de graphes.” 2015. Web. 14 Jul 2020.

Vancouver:

Neggazi B. Self-stabilizing algorithms for graph parameters : Algorithmes auto-stabilisants pour des paramètres de graphes. [Internet] [Doctoral dissertation]. Université Claude Bernard – Lyon I; 2015. [cited 2020 Jul 14]. Available from: http://www.theses.fr/2015LYO10041.

Council of Science Editors:

Neggazi B. Self-stabilizing algorithms for graph parameters : Algorithmes auto-stabilisants pour des paramètres de graphes. [Doctoral Dissertation]. Université Claude Bernard – Lyon I; 2015. Available from: http://www.theses.fr/2015LYO10041

3. Delcourt, Michelle Jeannette. Viewing extremal and structural problems through a probabilistic lens.

Degree: PhD, Mathematics, 2017, University of Illinois – Urbana-Champaign

This thesis focuses on using techniques from probability to solve problems from extremal and structural combinatorics. The main problem in Chapter 2 is determining the typical structure of t-intersecting families in various settings and enumerating such systems. The analogous sparse random versions of our extremal results are also obtained. The proofs follow the same general framework, in each case using a version of the Bollobás Set-Pairs Inequality to bound the number of maximal intersecting families, which then can be combined with known stability theorems. Following this framework from joint work with Balogh, Das, Liu, and Sharifzadeh, similar results for permutations, uniform hypergraphs, and vector spaces are obtained. In 2006, Barát and Thomassen conjectured that the edges of every planar 4-edge-connected 4-regular graph can be decomposed into disjoint copies of S3, the star with three leaves. Shortly afterward, Lai constructed a counterexample to this conjecture. Following joint work with Postle, in Chapter 3 using the Small Subgraph Conditioning Method of Robinson and Wormald, we find that a random 4-regular graph has an S3-decomposition asymptotically almost surely, provided we have the obvious necessary divisibility conditions. In 1988, Thomassen showed that if G is at least (2k-1)-edge-connected then G has a spanning, bipartite k-connected subgraph. In 1989, Thomassen asked whether a similar phenomenon holds for vertex-connectivity; more precisely: is there an integer-valued function f(k) such that every f(k)-connected graph admits a spanning, bipartite k-connected subgraph? In Chapter 4, as in joint work with Ferber, we show that every 1010k3 log n-connected graph admits a spanning, bipartite k-connected subgraph. Advisors/Committee Members: Balogh, Jozsef (advisor), Kostochka, Alexandr (Committee Chair), Kirkpatrick, Kay (committee member), Tserunyan, Anush (committee member).

Subjects/Keywords: Small subgraph conditioning method; Random regular graph; Intersecting families; Star decomposition; Structural graph theory; Extremal combinatorcs

…natural further direction; the same can be said about certain structural problems. Star… …G with out-degrees 0 or 3 corresponds to an S3 -decomposition of G (a decomposition… …referred to as the star with k leaves in the literature. A subgraph F ⊆ G is said to be spanning… …if V (F ) = V (G). For a fixed subgraph F ⊆ G, an F -decomposition is a… 

Page 1 Page 2 Page 3 Page 4 Page 5 Page 6 Page 7

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th Edition):

Delcourt, M. J. (2017). Viewing extremal and structural problems through a probabilistic lens. (Doctoral Dissertation). University of Illinois – Urbana-Champaign. Retrieved from http://hdl.handle.net/2142/97669

Chicago Manual of Style (16th Edition):

Delcourt, Michelle Jeannette. “Viewing extremal and structural problems through a probabilistic lens.” 2017. Doctoral Dissertation, University of Illinois – Urbana-Champaign. Accessed July 14, 2020. http://hdl.handle.net/2142/97669.

MLA Handbook (7th Edition):

Delcourt, Michelle Jeannette. “Viewing extremal and structural problems through a probabilistic lens.” 2017. Web. 14 Jul 2020.

Vancouver:

Delcourt MJ. Viewing extremal and structural problems through a probabilistic lens. [Internet] [Doctoral dissertation]. University of Illinois – Urbana-Champaign; 2017. [cited 2020 Jul 14]. Available from: http://hdl.handle.net/2142/97669.

Council of Science Editors:

Delcourt MJ. Viewing extremal and structural problems through a probabilistic lens. [Doctoral Dissertation]. University of Illinois – Urbana-Champaign; 2017. Available from: http://hdl.handle.net/2142/97669

.