To see the other types of publications on this topic, follow the link: Subdivision of Star graph.

Dissertations / Theses on the topic 'Subdivision of Star graph'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 47 dissertations / theses for your research on the topic 'Subdivision of Star graph.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.

1

Jackson, Penelope S. "Star sets and related aspects of algebraic graph theory." Thesis, University of Stirling, 1999. http://hdl.handle.net/1893/26690.

Full text
Abstract:
Let μ be an eigenvalue of the graph G with multiplicity k. A star set corresponding to μ in G is a subset of V(G) such that [x] = k and μ is not an eigenvalue of G - X. It is always the case that the vertex set of G can be partitioned into star sets corresponding to the distinct eigenvalues of G. Such a partition is called a star partition. We give some examples of star partitions and investigate the dominating properties of the set V (G) \ X when μ ε {-I, a}. The induced subgraph H = G - X is called a star complement for μ in G. The Reconstruction Theorem states that for a given eigenvalue μ
APA, Harvard, Vancouver, ISO, and other styles
2

Kosebinu, Kazeem A. "Partially Oriented 6-star Decomposition of Some Complete Mixed Graphs." Digital Commons @ East Tennessee State University, 2021. https://dc.etsu.edu/etd/3943.

Full text
Abstract:
Let $M_v$ denotes a complete mixed graph on $v$ vertices, and let $S_6^i$ denotes the partial orientation of the 6-star with twice as many arcs as edges. In this work, we state and prove the necessary and sufficient conditions for the existence of $\lambda$-fold decomposition of a complete mixed graph into $S_6^i$ for $i\in\{1,2,3,4\}$. We used the difference method for our proof in some cases. We also give some general sufficient conditions for the existence of $S_6^i$-decomposition of the complete bipartite mixed graph for $i\in\{1,2,3,4\}$. Finally, this work introduces the decomposition of
APA, Harvard, Vancouver, ISO, and other styles
3

Anzur, Matthew Paul. "k-star decomposition of lambda-fold complete multipartite graphs." Auburn, Ala., 2007. http://repo.lib.auburn.edu/07M%20Dissertations/ANZUR_MATTHEW_39.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Melinder, Victor. "Upper bounds on the star chromatic index for bipartite graphs." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-164938.

Full text
Abstract:
An area in graph theory is graph colouring, which essentially is a labeling of the vertices or edges according to certain constraints. In this thesis we consider star edge colouring, which is a variant of proper edge colouring where we additionally require the graph to have no two-coloured paths or cycles with length 4. The smallest number of colours needed to colour a graph G with a star edge colouring is called the star chromatic index of G and is denoted <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cchi'_%7Bst%7D(G)" />. This paper proves an upper bound of the star chromatic i
APA, Harvard, Vancouver, ISO, and other styles
5

Coutinho, Bruno Gabriel Coelho. "Kuramoto model aplicado a um star graph e a redes scale-free." Master's thesis, Universidade de Aveiro, 2011. http://hdl.handle.net/10773/9669.

Full text
Abstract:
Mestrado em Física<br>O trabalho realizado teve como objetivo tentar compreender o efeito de hubs no Kuramoto model, para tal foram analisados dois sistemas diferentes. No primeiro, o Kuramoto model foi aplicado a um hub isolado, revelando-se que, para as distribuições analisadas, a frequência natural do oscilador central desempenha um papel decisivo no comportamento do sistema. Se a diferença entre esta frequência e o valor médio das frequências naturais dos vizinhos do oscilador central for menor que um certo valor, não existe transição de fase no sistema. No entanto, se a diferença
APA, Harvard, Vancouver, ISO, and other styles
6

Tarhini, Batoul. "Oriented paths in digraphs and the S-packing coloring of subcubic graph." Electronic Thesis or Diss., Bourgogne Franche-Comté, 2023. http://www.theses.fr/2023UBFCK079.

Full text
Abstract:
Cette thèse de doctorat est divisée en deux parties principales: La partie I explore l'existence de chemins orientés dans les digraphes, cherchant à établir un lien entre le nombre chromatique d'un digraphe et l'existence de chemins orientés spécifiques en tant que sous-digraphes. Les digraphes contenus dans n'importe quel digraphe n-chromatique sont appelés n-universels. Nous examinons deux conjectures : la conjecture de Burr, qui affirme que chaque arbre orienté d'ordre n est (2n-2)-universel, et la conjecture d'El Sahili, qui déclare que chaque chemin orienté d'ordre n est n-universel. Pour
APA, Harvard, Vancouver, ISO, and other styles
7

Derakhshan, Parisa. "Automorphisms generating disjoint Hamilton cycles in star graphs." Thesis, Loughborough University, 2015. https://dspace.lboro.ac.uk/2134/16779.

Full text
Abstract:
In the first part of the thesis we define an automorphism φn for each star graph Stn of degree n-1, which yields permutations of labels for the edges of Stn taken from the set of integers {1,..., [n/2c]}. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known two-labelled Hamilton cycle H1 2(n) in Stn. The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies in computer science. All our results improve on the known bounds for numb
APA, Harvard, Vancouver, ISO, and other styles
8

Culver, Chance. "Decompositions of the Complete Mixed Graph by Mixed Stars." Digital Commons @ East Tennessee State University, 2020. https://dc.etsu.edu/etd/3782.

Full text
Abstract:
In the study of mixed graphs, a common question is: What are the necessary and suffcient conditions for the existence of a decomposition of the complete mixed graph into isomorphic copies of a given mixed graph? Since the complete mixed graph has twice as many arcs as edges, then an obvious necessary condition is that the isomorphic copies have twice as many arcs as edges. We will prove necessary and suffcient conditions for the existence of a decomposition of the complete mixed graphs into mixed stars with two edges and four arcs. We also consider some special cases of decompositions of the c
APA, Harvard, Vancouver, ISO, and other styles
9

Culver, Chance. "Decompositions of the Complete Mixed Graph by Mixed Stars." Digital Commons @ East Tennessee State University, 2008. https://dc.etsu.edu/etd/3782.

Full text
Abstract:
In the study of mixed graphs, a common question is: What are the necessary and suffcient conditions for the existence of a decomposition of the complete mixed graph into isomorphic copies of a given mixed graph? Since the complete mixed graph has twice as many arcs as edges, then an obvious necessary condition is that the isomorphic copies have twice as many arcs as edges. We will prove necessary and suffcient conditions for the existence of a decomposition of the complete mixed graphs into mixed stars with two edges and four arcs. We also consider some special cases of decompositions of the c
APA, Harvard, Vancouver, ISO, and other styles
10

Moura, Phablo Fernando Soares. "Graph colorings and digraph subdivisions." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/.

Full text
Abstract:
The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (I
APA, Harvard, Vancouver, ISO, and other styles
11

Neggazi, Brahim. "Self-stabilizing algorithms for graph parameters." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10041/document.

Full text
Abstract:
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,
APA, Harvard, Vancouver, ISO, and other styles
12

Malloy, Nicole Andrea. "Minimum Rank Problems for Cographs." BYU ScholarsArchive, 2013. https://scholarsarchive.byu.edu/etd/3873.

Full text
Abstract:
Let G be a simple graph on n vertices, and let S(G) be the class of all real-valued symmetric nxn matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The smallest rank achieved by a matrix in S(G) is called the minimum rank of G, denoted mr(G). The maximum nullity achieved by a matrix in S(G) is denoted M(G). For each graph G, there is an associated minimum rank class, MR(G) consisting of all matrices A in S(G) with rank A = mr(G). Although no restrictions are applied to the diagonal entries of matrices in S(G), sometimes diagonal entries
APA, Harvard, Vancouver, ISO, and other styles
13

Stewart, Craig R. "An Evolutionary Analysis of the Internet Autonomous System Network." Kent State University / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=kent1276550359.

Full text
APA, Harvard, Vancouver, ISO, and other styles
14

Bahalkeh, Esmaeil. "Efficient Algorithms for Calculating the System Matrix and the Kleene Star Operator for Systems Defined by Directed Acyclic Graphs over Dioids." Ohio University / OhioLINK, 2015. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1440116216.

Full text
APA, Harvard, Vancouver, ISO, and other styles
15

Mortada, Maidoun. "The b-chromatic number of regular graphs." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10116.

Full text
Abstract:
Les deux problèmes majeurs considérés dans cette thèse : le b-coloration problème et le graphe emballage problème. 1. Le b-coloration problème : Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. EL Sahili et Kouider demandent s'il est vrai que chaque graphe d-régulier G avec le périmètre au moins 5 satisfait b(G) = d + 1. Blidia, Maffray et Zemir ont montré que l
APA, Harvard, Vancouver, ISO, and other styles
16

Sehovic, Mirsad, and Markus Carlsson. "Nåbarhetstestning i en baneditor : En undersökning i hur nåbarhetstester kan implementeras i en baneditor samt funktionens potential i att ersätta manuell testning." Thesis, Linnéuniversitetet, Institutionen för datavetenskap (DV), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-36394.

Full text
Abstract:
Denna studie undersöker om det är möjligt att införa nåbarhetstestning i en baneditor. Testets syfte är att ersätta manuell testing, det vill säga att bankonstruktören inte ska behöva spela igenom banan för att säkerställa att denne kommer kunna nå alla nåbara positioner.För att kunna utföra studien skapas en enkel baneditor som testplattform. Vidare utförs en jämförande studie av flera alternativa algoritmer för att fastställa vilken som är mest passande för nåbarhetstestning i en baneditor.Resultatet från den jämförande studien visade att A* (A star) var den mest passande algoritmen för funk
APA, Harvard, Vancouver, ISO, and other styles
17

Chen, Min. "Vertex coloring of graphs via the discharging method." Thesis, Bordeaux 1, 2010. http://www.theses.fr/2010BOR14090/document.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos ré
APA, Harvard, Vancouver, ISO, and other styles
18

Bína, Vladislav. "Mnoharozměrná pravděpodobnostní rozdělení: Struktura a učení." Doctoral thesis, Vysoká škola ekonomická v Praze, 2010. http://www.nusl.cz/ntk/nusl-72677.

Full text
Abstract:
The thesis considers a representation of a discrete multidimensional probability distribution using an apparatus of compositional models, and focuses on the theoretical background and structure of search space for structure learning algorithms in the framework of such models and particularly focuses on the subclass of decomposable models. Based on the theoretical results, proposals of basic learning techniques are introduced and compared.
APA, Harvard, Vancouver, ISO, and other styles
19

Gulshan, Varun. "From interactive to semantic image segmentation." Thesis, University of Oxford, 2011. http://ora.ox.ac.uk/objects/uuid:706b648a-e5e7-4334-a456-0f0b5701dbc4.

Full text
Abstract:
This thesis investigates two well defined problems in image segmentation, viz. interactive and semantic image segmentation. Interactive segmentation involves power assisting a user in cutting out objects from an image, whereas semantic segmentation involves partitioning pixels in an image into object categories. We investigate various models and energy formulations for both these problems in this thesis. In order to improve the performance of interactive systems, low level texture features are introduced as a replacement for the more commonly used RGB features. To quantify the improvement obta
APA, Harvard, Vancouver, ISO, and other styles
20

Braz, Caio de Moraes. "Segmentação de imagens pela transformada imagem-floresta com faixa de restrição geodésica." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-01062016-104354/.

Full text
Abstract:
Vários métodos tradicionais de segmentação de imagens, como a transformada de watershed de marcado- res e métodos de conexidade fuzzy (Relative Fuzzy Connectedness- RFC, Iterative Relative Fuzzy Connected- ness - IRFC), podem ser implementados de modo eficiente utilizando o método em grafos da Transformada Imagem-Floresta (Image Foresting Transform - IFT). No entanto, a carência de termos de regularização de fronteira em sua formulação fazem com que a borda do objeto segmentado possa ser altamente irregular. Um modo de contornar isto é por meio do uso de restrições de forma do objeto, que favo
APA, Harvard, Vancouver, ISO, and other styles
21

Ghazal, Salman. "Étude de la conjecture de Seymour sur le second voisinage." Phd thesis, Université Claude Bernard - Lyon I, 2011. http://tel.archives-ouvertes.fr/tel-00744560.

Full text
Abstract:
Soit D un digraphe simple (sans cycle orienté de longueur 2 ). En 1990, P. Seymour a conjecturé que D a un sommet v avec un second voisinage extérieur au moins aussi grand que son (premier) voisinage extérieur [1]. Cette conjecture est connue sous le nom de la conjecture du second voisinage du Seymour (SNC). Cette conjecture, si elle est vraie, impliquerait, un cas spécial plus faible (mais important) de la conjecture de Caccetta et Häggkvist [2] proposé en 1978 : tout digraphe D avec un degré extérieur minimum au moins égale à jV (D)j=k a un cycle orienté de longueur au plus k. Le cas particu
APA, Harvard, Vancouver, ISO, and other styles
22

Mansilla, Lucy Alsina Choque. "Transformada imagem-floresta com funções de conexidade não suaves: pesos adaptativos, polaridade de borda e restrições de forma." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-17032014-121734/.

Full text
Abstract:
Segmentar uma imagem consiste em particioná-la em regiões relevantes para uma dada aplicação, como para isolar um objeto de interesse no domínio de uma imagem. A segmentação é um dos problemas mais fundamentais e desafiadores em processamento de imagem e visão computacional. Ela tem desempenhado um papel importante, por exemplo, na pesquisa em neurologia, envolvendo imagens de Ressonância Magnética (RM), para fins de diagnóstico e tratamento de doenças relacionadas com alterações na anatomia do cérebro humano. Métodos de segmentação baseados na transformada imagem- floresta (IFT, Image Fore
APA, Harvard, Vancouver, ISO, and other styles
23

Hsu, Hong-Chun, and 許弘駿. "Hamiltonian Properties of Star Graph Families." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/79351246812601427064.

Full text
Abstract:
博士<br>國立交通大學<br>資訊科學系<br>92<br>Interconnection networks have been an important research topic for parallel and distributed computer systems. We usually use a graph $G=(V,E)$ to represent a network''s topology where vertices represent processors and edges represent links between processors. There are a lot of interconnection network''s properties proposed in literature. Hamiltonian property is one of the important. Since processors or links may be failed sometimes, fault-tolerant hamiltonian properties are also concerned in many studies on network topologies. A path is a {\it hamilto
APA, Harvard, Vancouver, ISO, and other styles
24

Liu, Chiu-chu, and 劉秋祝. "Multicast Algorithms on Star Graph Interconnection Networks." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/77474808682863242184.

Full text
Abstract:
碩士<br>國立中山大學<br>應用數學研究所<br>84<br>Recently, the multicast communication problem in a network becomes highly demanded im many applications, such as parallel game algorithms, speech analysis and image processing problems. The multicat communication problem has been formulated as four different versions of graph theoretical problems: Steiner tree, multicast tree, multicast path and multicast cycle. All these four versions of multicast problems have been proved to be NP- complete on general grap
APA, Harvard, Vancouver, ISO, and other styles
25

Chiang, Jian-An, and 蔣健安. "A Study on the Star Graph Interconnection Network." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/58731181204446512787.

Full text
Abstract:
碩士<br>國立中山大學<br>應用數學研究所<br>81<br>In this thesis, we shall study the star graph interconnection network, which was proposed recently. the star graph structure is elegant compared to the well-known hypercube structure as we shall give a simple comparison. We shall investigate the characteristics of the star graph more deeply and lots of papers proposed for them. Besides, we shall point out some problems and phenomenon both on the properties and the algorithms proposed on the star graph. Th
APA, Harvard, Vancouver, ISO, and other styles
26

LIAO, WEN-HUA, and 廖文華. "A broadcasting algorithm in star graph interconnection networks." Thesis, 1992. http://ndltd.ncl.edu.tw/handle/80777545007283753549.

Full text
APA, Harvard, Vancouver, ISO, and other styles
27

Liu, Tung-Hsing, and 劉東興. "Wormhole Routing on the Star Graph Interconnection Network." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/74847907055683477565.

Full text
Abstract:
碩士<br>國立中山大學<br>應用數學系<br>85<br>A deadlock-free wormhole routing algorithm can be developed by using the concept of virtual channel. In this thesis, we first propose two wormhole routing algorithms on the star graph. The first one is minimal, fully adaptive, and deadlock-free and it requires [3n+1/4] virtual channels for per physical link. For the second algorithm, we make some restrictions on the routing path selection. Thus, it reduces the number of virtual channels to [n+1/2]. It is still minimal and deadlock-free. However, it is only partially adaptive. Then we propose a fault-tolera
APA, Harvard, Vancouver, ISO, and other styles
28

Chu, Ching, and 朱慶. "On the Diameter of the Unidirectional Star Graph." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/33680652706047949648.

Full text
Abstract:
碩士<br>國立中正大學<br>資訊工程研究所<br>100<br>The star graph has been recognized as an attractive alternative to the hypercube. It possesses many attractive topological properties, such as recursive structure, symmetry, maximal fault tolerance and a simple routing algorithm. In addition, the unidirectional star graph also supports high speed networking and high performance distributed computing. Motivated by the investigations on the unidirectional interconnection networks, this paper improves the previous result on routing in USn. In this paper, we recursively analyze the cycle structu
APA, Harvard, Vancouver, ISO, and other styles
29

Wang, Nen-Chung, and 王能中. "Multicast Algorithms in Wormhole-Routed Star Graph Interconnection Networks." Thesis, 1998. http://ndltd.ncl.edu.tw/handle/85715218751750231055.

Full text
Abstract:
碩士<br>國立成功大學<br>資訊工程學系<br>86<br>Parallel processing technique has become important because it supports high-performance computation. So, massively parallel processing computers connected by a variety of interconnection networks are increasingly demanded for high-performance computation-based applications. Multicast, an important communication mechanism, is frequently used in many applications of parallel computing. The star graph interconnection network, when compared with the hypercube net
APA, Harvard, Vancouver, ISO, and other styles
30

Tseng, Chun-Hong, and 曾俊宏. "Routing Algorithm and Diameter for the Unidirectional Star Graph." Thesis, 2007. http://ndltd.ncl.edu.tw/handle/53816271994933707171.

Full text
Abstract:
碩士<br>國立中正大學<br>資訊工程所<br>96<br>In this paper, we propose a routing algorithm between any two nodes in the unidirectional star graph upon the specific cycle representation, called the feasible routing cycle structure (RCS), which is equivalently transformed from the cycle structure. We prove that the feasible routing path can accomplish the routing effectively in the unidirectional n-star graph USn, and also derive that the diameter is no more than 2n for n 5 in USn. We also show that our routing algorithm could be performed in time O(n2). The result shows a great improvement to the correspondi
APA, Harvard, Vancouver, ISO, and other styles
31

Lin, Chang Wu, and 章戊霖. "Efficient Broadcasting Algorithms in the Star Graph Interconnection Networks." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/51938031584022053844.

Full text
Abstract:
碩士<br>國立中央大學<br>資訊及電子工程研究所<br>83<br>P狀圖連結網路 ( star graph interconnection networks) 是除了 維立 方體 ( hypercube) 外另一種新的網路架構。對於相同個數的 理器,它 比超維立方體有較少的連結線 (link) 和較少的通訊延遲communication delay) 。廣播(broadcasting)是一個很重要的演算k,在許多平行演算法 中,如線性代數、資料庫搜尋和線性程式演算k中廣泛地被使用。因此一 個有效率的廣播演算法 ( broadcastinglgorithm) 是非常的重要。b本 篇論文中,我們在星狀圖網路單埠模型 ( single-port model )U提出兩 個有效率的廣播演算法,分別為多對多的個人化廣播式演算k (all-to- all personalized broadcasting algorithm) ,另一則隻h對多的非個人 化廣播式演算法 ( all-to-all non-personali
APA, Harvard, Vancouver, ISO, and other styles
32

Tai, Keng-Sheng, and 戴耿聖. "Near-Optimal Broadcasting in a (n, k)-Star Graph." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/67460217179859379485.

Full text
Abstract:
碩士<br>中華大學<br>電機工程學系碩士班<br>87<br>This thesis presents a broadcasting algorithm in a(n, k)-star graph based on a proposed scattering-then-flooding strategy. The scattering-then-flooding strategy is analogous to divide-and-conquer scheme, is divided into scattering and flooding phases. First, the scattering phase is to recursively split original message into submessages and scatter each submessage to all other subgraphs unitl subgraphs are complete graphs. The scattering phase is a top-down approach. Second, the flooding phase is recursively to flood submessages to all other subgraphs to acquire
APA, Harvard, Vancouver, ISO, and other styles
33

Pan, PoSheng, and 潘伯陞. "Diagnosis Algorithm on the Star Graph under the PMC Model." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/20703187588653568641.

Full text
Abstract:
碩士<br>靜宜大學<br>資訊工程學系<br>99<br>In this paper, we propose a specific structure in the star graph for local diagnosis under the PMC model. We design an adaptive local diagnosis algorithm for a star graph S n .We prove that S n is (n-1) diagnosable with our proposed algorithm under the PMC model. Moreover, with our algorithm, a diagnosis is completed in three test rounds.
APA, Harvard, Vancouver, ISO, and other styles
34

LI, ZHEN-MING, and 李振銘. "All-to-all broadcasting algorithms on star graph interconnection network." Thesis, 1993. http://ndltd.ncl.edu.tw/handle/37465524589124043904.

Full text
APA, Harvard, Vancouver, ISO, and other styles
35

Tian-shiang, Harng, and 韓天祥. "Virtual-Channel-Based Broadcasting Algorithms on the Star Graph Interconnection Network." Thesis, 1998. http://ndltd.ncl.edu.tw/handle/94861670093012184391.

Full text
Abstract:
碩士<br>國立中山大學<br>應用數學研究所<br>86<br>A broadcasting algorithm based on the virtual channels can be developed by using the concept of relay trees. In this thesis, we propose four broadcasting algorithms for the star graph and the incomplete star graph. The first one is broadcasting in the star graph. The second algorithm is broadcasting in the incomplete star graph. Then we consider about message redundancy in broadcasting, and two broadcasting algorithms without message redundancy on the stargraph and the incomplete star graph are proposed. They all requires [(n+1)/2] irtual channels for each ph
APA, Harvard, Vancouver, ISO, and other styles
36

Wang, Neng-Chung, and 王能中. "Efficient Multicasting Strategies on Wormhole-Routed Star Graph and Irregular Networks." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/zz967r.

Full text
Abstract:
博士<br>國立成功大學<br>資訊工程學系碩博士班<br>90<br>Parallel processing technique has become important because it supports high-performance computation. So, massively parallel processing systems (MPPs) connected by a variety of interconnection networks are increasingly demanded for high-performance computation-based applications. Multicast is an important collective communication operation on multicomputer systems, in which the same message is delivered from a source node to an arbitrary number of destination nodes. The star graph [2, 3] interconnection network has been recognized as an attractive alternat
APA, Harvard, Vancouver, ISO, and other styles
37

Shyan, Chen Yuh, and 陳裕賢. "Algorithm-Based Fault-Tolerant Strategies in Faulty Hypercube and Star Graph Multicomputers." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/52093418085298365197.

Full text
Abstract:
博士<br>國立中央大學<br>資訊及電子工程研究所<br>84<br>This dissertation addresses the design of algorithm- based fault-tolerant strategies in faulty hypercube and star graph multicomputers without hardware modification. Several new concepts and designs are presented here under the permanent and transient fault models. Under the permanent fault model, we propose a new fault- tolerant reconfiguration scheme in the faulty hypercube and star graph multicomputers. Our reconfiguration scheme is t
APA, Harvard, Vancouver, ISO, and other styles
38

Hsieh, Yi-Lin, and 謝易霖. "Fault Hamiltonicity and fault Hamiltonian connectivity of The (n, k)-star graph." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/56349980942541777977.

Full text
Abstract:
碩士<br>國立交通大學<br>資訊科學系<br>90<br>In this paper, we consider the fault hamiltonicity and fault hamiltonian connectivity of the (n, k)-star graph Sn,k. Assume that F  V(Sn,k)  E(Sn,k). For n — k  2, we prove that Sn,k — F is hamiltonian if |F | ≤ n — 3 and Sn,k — F is hamiltonian connected if |F | < n — 4. For n — k = 1, Sn,n-1 is isomorphic to the star graph Sn and it is Known that Sn is hamiltonian if and only if n > 2 and Sn is hamiltonian connected if and only if n = 2. Moreover, all the bounds are tight.
APA, Harvard, Vancouver, ISO, and other styles
39

Chang, Chin-Hua, and 張晉華. "A Study of Fault-Tolerant Routing on Star Graph Using Limited- Global-Information." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/47163772362489807277.

Full text
Abstract:
碩士<br>國立台灣工業技術學院<br>電機工程技術研究所<br>85<br>In this thesis, we study the problem of fault-tolerant communication in star graphs multicomputers in which components may fail. We propose the concept of safety levels which respect to the distance to nearest faulty node of each direction. A simple algorithm is presented to calculate the safety levels of each processor that in system. A routing algorithm which based on safety levels is then presented to facilitate efficient fault-tolerant routing. Th
APA, Harvard, Vancouver, ISO, and other styles
40

Ren, Shi Min, and 任世敏. "Efficient all-to-all broadcasting in the hypercube and star graph interconnection networks." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/98189246772016886186.

Full text
APA, Harvard, Vancouver, ISO, and other styles
41

Du, Ming Zhi, and 杜明智. "A study of multicast problem in the hypercube and star graph interconnection networks." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/45557925820224954814.

Full text
APA, Harvard, Vancouver, ISO, and other styles
42

Chiu, Chiao-Wei, and 邱喬偉. "A Fault-Tolerant Routing Algorithm with Probabilistic Safety Vectors on the (n, k)-star Graph." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/u99jrh.

Full text
Abstract:
碩士<br>國立中山大學<br>資訊工程學系研究所<br>96<br>In this thesis, we focus on the design of the fault-tolerant routing algorithm for the (n, k)-star graph. We apply the idea of collecting the limited global information used for routing on the n-star graph to the (n, k)-star graph. First, we build the probabilistic safety vector (PSV) with modified cycle patterns. Then, our routing algorithm decides the fault-free routing path with the help of PSV. In order to improve the routing performance with more faulty nodes, we dynamically assign the threshold for our routing algorithm. The performance is judged by the
APA, Harvard, Vancouver, ISO, and other styles
43

Wei-HaoDeng and 鄧偉豪. "Topological Properties and Conditional Diagnosability of(n,k)-star Graph Under the Comparison Diagnosis Model." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/95873051168710359375.

Full text
Abstract:
碩士<br>國立成功大學<br>資訊工程學系碩博士班<br>100<br>Let Sn be the n-star graph with degree n, and there is an enhanced version of Sn, called (n,k)-star graph, denoted by Sn,k. The (n,k)-star graph was proposed in 1995 by W.K. Chiang et al. In recent years, diagnosis has been one of the most important issue as the size of multiprocessor system grows rapidly. Conditional diagnosability is a new measure of diagnosability introduced by Lai et al. It is a better method to measure the diagnosability of regular interconnection networks. This thesis shows that the conditional diagnosability of (n,k)-star graph is n+
APA, Harvard, Vancouver, ISO, and other styles
44

Hon, Min Hor, and 洪明豪. "Algorithms for Finding Vertex-disjoint Paths and Edge-disjoint Spanning Trees in Star Graph Interconnection Networks Work Management System." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/47729401399593481665.

Full text
APA, Harvard, Vancouver, ISO, and other styles
45

Xu, Zhi. "The Frobenius Problem in a Free Monoid." Thesis, 2009. http://hdl.handle.net/10012/4574.

Full text
Abstract:
Given positive integers c1,c2,...,ck with gcd(c1,c2,...,ck) = 1, the Frobenius problem (FP) is to compute the largest integer g(c1,c2,...,ck) that cannot be written as a non-negative integer linear combination of c1,c2,...,ck. The Frobenius problem in a free monoid (FPFM) is a non-commutative generalization of the Frobenius problem. Given words x1,x2,...,xk such that there are only finitely many words that cannot be written as concatenations of words in {x1,x2,...,xk}, the FPFM is to find the longest such words. Unlike the FP, where the upper bound g(c1,c2,...,ck)≤max 1≤i≤k ci2 is quadratic, t
APA, Harvard, Vancouver, ISO, and other styles
46

Melka, Jakub. "Výpočetní složitost v teorii grafů." Master's thesis, 2011. http://www.nusl.cz/ntk/nusl-379578.

Full text
Abstract:
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the recons
APA, Harvard, Vancouver, ISO, and other styles
47

Pacheco, Maria de Fátima Moreira da Silva. "Recognition of graphs with convex quadratic stability number." Doctoral thesis, 2019. http://hdl.handle.net/10773/29883.

Full text
Abstract:
A maximum stable set is a stable set with the largest possible size, for a given graph G. This size is called the stability number of G, and it is denoted α(G). The problem of determining the stability number of an arbitrary graph, is a NP-complete optimization problem. As such, it is unlikely that there is a polynomial algorithm for finding a maximum stable set of a graph. The main purpose of this thesis is the achievement of recognition algorithms for graphs with convex quadratic stability number that are graphs whose stability number is equal to the optimal value of a convex quadrati
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!