To see the other types of publications on this topic, follow the link: Hypercuts.
Dissertations / Theses on the topic 'Hypercuts'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Hypercuts.'
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
John, Ajita. "Linearly Ordered Concurrent Data Structures on Hypercubes." Thesis, University of North Texas, 1992. https://digital.library.unt.edu/ark:/67531/metadc501197/.
Full textAbstract:
This thesis presents a simple method for the concurrent manipulation of linearly ordered data structures on hypercubes. The method is based on the existence of a pruned binomial search tree rooted at any arbitrary node of the binary hypercube. The tree spans any arbitrary sequence of n consecutive nodes containing the root, using a fan-out of at most [log₂ 𝑛] and a depth of [log₂ 𝑛] +1. Search trees spanning non-overlapping processor lists are formed using only local information, and can be used concurrently without contention problems. Thus, they can be used for performing broadcast and merge operations simultaneously on sets with non-uniform sizes. Extensions to generalized and faulty hypercubes and applications to image processing algorithms and for m-way search are discussed.
2
潘忠強 and Chung-keung Poon. "Fault tolerant computing on hypercubes." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1991. http://hub.hku.hk/bib/B31209944.
Full text
3
Hartman, Jonathan Edward. "Hypercube solutions for conjugate directions." Thesis, Monterey, California. Naval Postgraduate School, 1991. http://hdl.handle.net/10945/26581.
Full textAbstract:
As computing machines advance, new fields are explored and old ones are expanded. This thesis considers parallel solutions to several well-known problems from numerical linear algebra, including Gauss Factorization and the method of Conjugate Gradients. The Gauss algorithm was implemented on two parallel machines: an Intel iPSC/2, and a network of INMOST-800 transputers. Interprocessor communication-in both cases-was borne by a hypercube interconnection topology. The results reveal general findings from parallel computing and more specific data and information concerning the systems and algorithms that were employed. Communication is timed and the results are analyzed, showing typical features of a message passing system. System performance is illustrated by results from the Gauss codes. The use of two different pivoting strategies shows the potential and the limitations of a parallel machine. The iPSC/2 and transputer systems both show excellent parallel performance when solving large, dense, unstructured systems. Differences, advantages, and disadvantages of these two systems are examined and expectations for current and future machines are discussed
4
Pinto, Trevor Alvaro Anthony. "Extremal problems on the hypercube." Thesis, Queen Mary, University of London, 2016. http://qmro.qmul.ac.uk/xmlui/handle/123456789/23651.
Full textAbstract:
The hypercube, Qd, is a natural and much studied combinatorial object, and we discuss various extremal problems related to it. A subgraph of the hypercube is said to be (Qd; F)-saturated if it contains no copies of F, but adding any edge forms a copy of F. We write sat(Qd; F) for the saturation number, that is, the least number of edges a (Qd; F)-saturated graph may have. We prove the upper bound sat(Qd;Q2) < 10 2d, which strongly disproves a conjecture of Santolupo that sat(Qd;Q2) = 1 4 + o(1) d2d 1. We also prove upper bounds on sat(Qd;Qm) for general m. Given a down-set A and an up-set B in the hypercube, Bollobás and Leader conjectured a lower bound on the number of edge-disjoint paths between A and B in the directed hypercube. Using an unusual form of the compression argument, we confirm the conjecture by reducing the problem to a the case of the undirected hypercube. We also prove an analogous conjecture for vertex-disjoint paths using the same techniques, and extend both results to the grid. Additionally, we deal with subcube intersection graphs, answering a question of Johnson and Markström of the least r = r(n) for which all graphs on n vertices may be represented as subcube intersection graph where each subcube has dimension exactly r. We also contribute to the related area of biclique covers and partitions, and study relationships between various parameters linked to such covers and partitions. Finally, we study topological properties of uniformly random simplicial complexes, employing a characterisation due to Korshunov of almost all down-sets in the hypercube as a key tool.
5
Park, Jahng Sun. "The Folded Hypercube ATM Switches." Diss., Virginia Tech, 2001. http://hdl.handle.net/10919/29167.
Full textAbstract:
Over the past few years, many high performance asynchronous transfer mode (ATM) switches have been proposed. The majority of these switches have high performance but also high hardware complexity. Therefore, there is a need for switch designs with low complexity and high performance. This research proposes three new ATM switches based on the folded hypercube network (FHC). The performance of the three architectures are studied using a network model and simulation. The major performance parameters measured are the cell loss rate and cell delay time through the switch under uniform, normal, and bursty traffic patterns. To guarantee faster switching of time-sensitive cells, the routing algorithm of the three switches uses a priority scheme that gives higher precedence to the time-sensitive cells. Also, an output buffer controller is designed to manage the buffers in a fair manner. The three proposed switch architectures have lower complexity while providing equivalent or better switching performance compared to other more complex ATM switches described in the literature. This research shows a new approach to designing ATM switches by using the FHC as the switching fabric for the first time instead of using the crossbar, multi-path, or Banyan-based switching fabrics.<br>Ph. D.
6
White, William Warren. "Mapping parallel algorithms into hypercubes /." The Ohio State University, 1989. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487676261010809.
Full text
7
Zhu, Yahui. "Job scheduling on a hypercube /." The Ohio State University, 1990. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487686243822801.
Full text
8
Johansson, Per. "Avoiding edge colorings of hypercubes." Thesis, Linköpings universitet, Matematik och tillämpad matematik, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-160863.
Full textAbstract:
The hypercube Qn is the graph whose vertices are the ordered n-tuples of zeros and ones, where two vertices are adjacent iff they differ in exactly one coordinate. A partial edge coloring f of a graph G is a mapping from a subset of edges of G to a set of colors; it is called proper if no pair of adjacent edges share the same color. A (possibly partial and unproper) coloring f is avoidable if there exists a proper coloring g such that no edge has the same color under f and g. An unavoidable coloring h is called minimal if it would be avoidable by letting any colored edge turn noncolored. We construct a computer program to find all minimal unavoidable edge colorings of Q3 using up to 3 colors, and draw some conclusions for general Qn.
9
Lin, Eileen Tien. "Join processing on a hypercube multicomputer." Diss., Georgia Institute of Technology, 1990. http://hdl.handle.net/1853/8206.
Full text
10
Gurney, Kevin. "Learning in networks of structured hypercubes." Thesis, Brunel University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.328877.
Full text
11
Abali, Bulent. "Parallel sorting algorithms for hypercube multiprocessors /." The Ohio State University, 1989. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487672631602736.
Full text
12
Florkowski, Stanley F. "Spectral graph theory of the Hypercube." Thesis, Monterey, Calif. : Naval Postgraduate School, 2008. http://edocs.nps.edu/npspubs/scholarly/theses/2008/Dec/08Dec%5FFlorkowski.pdf.
Full textAbstract:
Thesis (M.S. in Applied Mathematics)--Naval Postgraduate School, December 2008.<br>Thesis Advisor(s): Rasmussen, Craig W. "December 2008." Description based on title screen as viewed on January 29, 2009. Includes bibliographical references (p. 51-52). Also available in print.
13
Kobeissi, Mohamed. "Plongement de graphes dans l'hypercube." Phd thesis, Grenoble 1, 2001. https://theses.hal.science/tel-00004683.
Full textAbstract:
Le but principal de ce manuscrit est de montrer que certaines familles de graphes sont des graphes plongeables dans l'hypercube. Un problème d'une autre nature sera traité, il concerne la partition de l'hypercube en des cycles sommet-disjoints de longueur paires. Nous prouvons que l'hypercube de dimension n peut être partitionné en k cycles sommet-disjoints si k<n-1, et qui utilisent des arêtes de même direction dans l'hypercube. Le problème de plongement de graphes dans l'hypercube fera l'objet du dernier chapitre. Dans ce chapitre, nous introduisons une nouvelle famille de graphes, les MD-graphes. Nous avons montré que les quasi-étoiles et les double quasi-étoiles sont des graphes plongeables dans certain MD-graphes. Nous avons réussi à montrer que les MD-graphes sont des graphes plongeables dans l'hypercube, ce qui nous remontre que les quasi-étoiles, mais également montre que les double quasi-étoiles sont des graphes plongeables dans Qn. Ce qui résout un problème ouvert posé par Ivan Havel depuis 1984
14
Mollard, Michel Laborde Jean-Marie Benzaken Claude Payan Charles. "Quelques problèmes combinatoires sur l'hypercube et les graphes de Hamming." S.l. : Université Grenoble 1, 2008. http://tel.archives-ouvertes.fr/tel-00333335.
Full text
15
Smedley, Garth Peter. "Algorithms for embedding binary trees into hypercubes." Thesis, University of British Columbia, 1989. http://hdl.handle.net/2429/27635.
Full textAbstract:
The problem of embedding a guest graph G into a host graph H arises in the process of mapping a parallel program to a multicomputer. The communication structure of the program is represented by G, the interconnection network of the multicomputer is represented by H and the goal is to embed G into H such that some measure of the communication cost is minimized. In general, this problem is N P-complete and several types of approximation algorithms have been proposed. We evaluate these algorithms empirically using hypercube host graphs and binary tree guest graphs. These families of graphs are interesting because of the existence of both heuristic techniques and theoretical algorithms for this problem. Although for general trees the problem is N P-complete, for binary trees the complexity remains open. We have implemented and experimented with several different algorithms and discovered variations of a greedy approach which produce close to optimal solutions in a reasonable amount of time.<br>Science, Faculty of<br>Computer Science, Department of<br>Graduate
16
Mukhopadhyaya, Utpal Kanti. "Deflection routing in buffered binary hypercube switches." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp02/NQ32794.pdf.
Full text
17
Chakraborty, Amal. "Parallel homotopy curve tracking on a hypercube." Diss., This resource online, 1990. http://scholar.lib.vt.edu/theses/available/etd-09162005-115011/.
Full text
18
Lehman, Eric (Eric Allen) 1970. "Deadlock-free routing in a faulty hypercube." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/47503.
Full text
19
Aliakbarpour, Maryam. "Learning and testing junta distributions over hypercubes." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/101578.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.<br>Cataloged from PDF version of thesis.<br>Includes bibliographical references (pages 77-80).<br>Many tasks related to the analysis of high-dimensional datasets can be formalized as problems involving learning or testing properties of distributions over a high-dimensional domain. In this work, we initiate the study of the following general question: when many of the dimensions of the distribution correspond to "irrelevant" features in the associated dataset, can we learn the distribution efficiently? We formalize this question with the notion of junta distribution. The distribution D over {0, 1}n is a k-junta distribution if the probability mass function p of D is a k-junta-- i. e., if there is a set J [subset][n] of at most k coordinates such that for every x [set membership] {0, 1}7, the value of p(x) is completely determined by the value of x on the coordinates in J. We show that it is possible to learn k-junta distributions with a number of samples that depends only logarithmically on the total number n of dimensions. We give two proofs of this result; one using the cover method and one by developing a Fourier-based learning algorithm inspired by the Low-Degree Algorithm of Linial, Mansour, and Nisan (1993). We also consider the problem of testing whether an unknown distribution is a k-junta distribution. We introduce an algorithm for this task with sample complexity Õ(2n/²k⁴) and show that this bound is nearly optimal for constant values of k. As a byproduct of the analysis of the algorithm, we obtain an optimal bound on the number of samples required to test a weighted collection of distribution for uniformity. Finally, we establish the sample complexity for learning and testing other classes of distributions related to junta-distributions. Notably, we show that the task of testing whether a distribution on {0, 1}n contains a coordinate i [set membership] [n] such that xi is drawn independently from the remaining coordinates requires [theta]](2²n/³) samples. This is in contrast to the task of testing whether all of the coordinates are drawn independently from each other, which was recently shown to have sample complexity [theta](2n/²) by Acharya, Daskalakis, and Kamath (2015).<br>by Maryam Aliakbarpour.<br>S.M.
20
Polit, Montes de Oca Esteban. "Une n-acp d'un hypercube de donnees." Grenoble 2, 1986. http://www.theses.fr/1986GRE21015.
Full textAbstract:
Extension du modele tucker3 pour l'analyse de cubes a plus de 3 modes. Utilisation d'une approche geometrique qui permet l'introduction de metriques dans chaque mode. On associe a un hypercube de donnees une forme n-lineaire qu'on approche par une forme n-lineaire de rang plus petit pouvant etre associee a un hypercube de dimensions reduites. Presentation d'un algorithme nomme tuckalsn pour resoudre ce probleme d'approximation. Tuckalsn est une extension de l'algorithme iteratif tuckals3 de kroonenberg et de leeuw. Definition des composantes principales de la n-acp. Elles sont une generalisation des cp de l'acp, et elles s'interpretent de facon analogue. Certaines proprietes d'optimalite sont respectees. On propose des representations graphiques pour les modes et des indices pour mesurer la fidelite avec laquelle la forme n-lineaire permet de reproduire le n-cube original de donnees<br>The model proposed by tucker for analysing 3 modes data sets is extended to the n-modes setting and metrics are introduced for analysing each mode. One assotiates an n-linear form to each n-mode data set and approches by an n-linear form of smaller rank, that defines a n-mode data set of reduced sizes, easier to analyse. We propose an algorithm named tuckalsn that solves the approximation problem involved in extending the iterative process given by kroonenberg and de leeuw. The latent variables, so obtained, are shown to extenoed principal components built by usual 2 modes pca, and received analogous interpretations. We discuss too the optimality properties of usual pca that remain true or not in the n-modes setting. Graphical representations as well as interpretative tools for reading them are proposed, such as indices meaning the global and elementwise quality and reliability of the approximation
21
Phillips, Bo. "Symmetric Colorings of the Hypercube and Hyperoctahedron." Wright State University / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=wright1460642665.
Full text
22
Cairncross, Emily. "Proper 3-colorings of cycles and hypercubes." Oberlin College Honors Theses / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=oberlin1621606265779497.
Full text
23
Polit, Montes de Oca Esteban. "Une n-ACP d'un hypercube de données." Grenoble 2 : ANRT, 1986. http://catalogue.bnf.fr/ark:/12148/cb376004830.
Full text
24
Fisher, Jennette Caryl. "Algorithms for the identification of maximal fault-free paths and cycles in faulty hypercubes /." Abstract, 2008. http://eprints.ccsu.edu/archive/00000518/01/1941ABSTR.htm.
Full textAbstract:
Thesis (M.A.) -- Central Connecticut State University, 2008.<br>Thesis advisor: Nelson Castañeda. "... in partial fulfillment of the requirements for the degree of Master of Arts in Mathematical Sciences." Includes bibliographical references (leaf 32). Also available via the World Wide Web.
25
Lantz, Emilott. "What can Turán tell us about the hypercube?" Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-57789.
Full textAbstract:
The Turán problem is a fundamental problem in extremal graph theory. It asks what the maximum number of edges a given graph G can have, not containing some forbidden graph H, and is solved using the Turán number ex(n,H), density π(H) and graph Tr(n). Turán's theorem tells us that the Turán graph Tr(n) is the largest Kr+1-free simple graph on n vertices. This paper is an overview of Turán problems for cliques Kn, hypercubes Qn and Hamming graphs H(s,d). We end it by proving a new result we call "the layer theorem", solving the Hamming-Turán problem using a method of creating layers of vertices in a graph. This theorem gives a lower bound for the Hamming-relative Turán density as follows: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cpi_%7Bs,d%7D(%5Cmathcal%7BH%7D_%7Bs,d%7D,F)%20%5Cgeq%201%20-%20%5Cdfrac%7Bf+g%7D%7B%7C%7CH(s,d)%7C%7C%7D" /> where <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?f%20=%20%5Cbinom%7Bs%7D%7B2%7D%5Cleft(1-%5Cdfrac%7Br-2%7D%7Br-1%7D%5Cright)ds%5E%7Bd-1%7D%20%5Ctext%7B%20and%20%7D%20g%20=%20%5Csum_%7Bi=1%7D%5E%7Bn/(t-1)%7D%20(d-i(t-1))(s-1)%5E%7Bi(t-1)+1%7D%5Cbinom%7Bd%7D%7Bi(t-1)%7D" /> for the forbidden graph F stretching over t layers and r = χ(F).<br>Turán-problemet är det fundamentala problemet inom extremal grafteori. Det ställer frågan vad det maximala antalet kanter en given graf G kan ha utan att innehålla någon förbjuden graf H, och löses med hjälp av Turán-talet ex(n,H), -densiteten π(H) and -grafen Tr(n). Turáns sats säger oss att Turán-grafen Tr(n) är den största Kr+1-fria enkla grafen på n hörn. Denna uppsats är en överblick av Turán-problem i klickar Kn, hyperkuber Qn och Hamming-grafer H(s,d). Vi avslutar den med att bevisa ett nytt resultat som vi kallar "lagersatsen", vilket löser Hamming-Turán-problemet med hjälp av en metod som skapar lager av hörnen i en graf. Lagersatsen ger en undre gräns för den Hamming-relativa Turán-densiteten enligt följande: <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?%5Cpi_%7Bs,d%7D(%5Cmathcal%7BH%7D_%7Bs,d%7D,F)%20%5Cgeq%201%20-%20%5Cdfrac%7Bf+g%7D%7B%7C%7CH(s,d)%7C%7C%7D" /> där <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?f%20=%20%5Cbinom%7Bs%7D%7B2%7D%5Cleft(1-%5Cdfrac%7Br-2%7D%7Br-1%7D%5Cright)ds%5E%7Bd-1%7D%20%5Ctext%7B%20and%20%7D%20g%20=%20%5Csum_%7Bi=1%7D%5E%7Bn/(t-1)%7D%20(d-i(t-1))(s-1)%5E%7Bi(t-1)+1%7D%5Cbinom%7Bd%7D%7Bi(t-1)%7D" /> för den förbjudna grafen F som sträcker sig över t lager samt r = χ(F).
26
Lim, Choon Kee. "Hypercube machine implementation of low-level vision algorithms." Ohio : Ohio University, 1989. http://www.ohiolink.edu/etd/view.cgi?ohiou1182864143.
Full text
27
Rix, James Gregory. "Hypercube coloring and the structure of binary codes." Thesis, University of British Columbia, 2008. http://hdl.handle.net/2429/2809.
Full textAbstract:
A coloring of a graph is an assignment of colors to its vertices so that no
two adjacent vertices are given the same color. The chromatic number of a
graph is the least number of colors needed to color all of its vertices. Graph
coloring problems can be applied to many real world applications, such as
scheduling and register allocation. Computationally, the decision problem
of whether a general graph is m-colorable is NP-complete for m ≥ 3.
The graph studied in this thesis is a well-known combinatorial object,
the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all
k; however, coloring the square of the cube is a much more interesting problem.
This is the graph in which the vertices are binary vectors of length k,
and two vertices are adjacent if and only if the Hamming distance between
the two vectors is at most 2.
Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis
will begin with an introduction to binary codes and their structure. One
of the most fundamental combinatorial problems is finding optimal binary
codes, that is, binary codes with the maximum cardinality satisfying a specified
length and minimum distance. Many upper and lower bounds have
been produced, and we will analyze and apply several of these. This leads
to many interesting results about the chromatic number of the square of the
cube.
The smallest k for which the chromatic number of Q2k is unknown is
k = 8; however, it can be determined that this value is either 13 or 14.
Computational approaches to determine the chromatic number of Q28 were
performed. We were unable to determine whether 13 or 14 is the true value;
however, much valuable insight was learned about the structure of this graph
and the computational difficulty that lies within. Since a 13-coloring of Q28
must have between 9 and 12 color classes being (8; 20; 3) binary codes, this
led to a thorough investigation of the structure of such binary codes.
28
Vasquez, Maria Rosario. "An investigation of super line graphs of hypercubes." Virtual Press, 1993. http://liblink.bsu.edu/uhtbin/catkey/865951.
Full textAbstract:
Graphs, as mathematical objects, play a dominant role in the study of network modeling, VLSI design, data structures, parallel computation, process scheduling and in a variety of other areas of computer science. Hypercubes are one of the preferred architectures for parallel computation, and a study of some properties of the hypercubes motivated this thesis.The concept of super line graphs, introduced by Bagga at el, generalizes the notion of line graphs. In this thesis several graph theoretic properties of super line graphs of hypercubes are studied. In particular the super line graphs of index two of hypercubes are investigated and some exact results and precise characterizations are found.<br>Department of Computer Science
29
Fu, Jung-Sheng, and 傅榮勝. "Embedding mesh of the trees into hypercube and incomplete hypercube." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/29861060600169882021.
Full text
30
Lai, Cheng-Nan, and 賴正男. "One-to-Many Disjoint Paths in the Hypercube and Folded Hypercube." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/10534671366993862740.
Full textAbstract:
博士<br>國立臺灣大學<br>資訊工程學研究所<br>89<br>Abstract
Routing is a process of transmitting messages among nodes. Efficient and reliable routing can be achieved by using disjoint paths, because they can be used to avoid communication bottleneck, increase the efficiency of message transmission, and provide alternative transmission routes. In this thesis, a new routing strategy, named routing function, is introduced. We show the effectiveness of routing functions by achieving the following results. First, we construct a maximal number of one-to-many disjoint paths in the hypercube and folded hypercube whose lengths are not greater than the diameters plus one. Besides, each path has length at most the distance of the two end nodes plus two. As a by-product, the Rabin number and strong Rabin number of the hypercube and folded hypercube can be obtained. Liaw and Chang left it open to compute the Rabin number and strong Rabin number of the folded hypercube. Second, we compute the w-Rabin number and strong w-Rabin number of the hypercube and folded hypercube, where w is smaller than the node connectivity. Third, we construct one-to-many disjoint paths in the hypercube whose total length is minimized.
31
ZENG, ZHI-WEN, and 曾志文. "Five-round Adaptive Diagnosis on Hypercubes, Crossed-cubes, and Exchanged Hypercubes." Thesis, 2018. http://ndltd.ncl.edu.tw/handle/6yg595.
Full textAbstract:
碩士<br>明新科技大學<br>資訊管理系碩士班<br>106<br>In large networks or multi-processor systems, failure of some nodes may lead to a breakdown of the entire network or system. Thus, to diagnose the faulty nodes in large networks or multi-processor systems plays an extremely important role. The technique of using the test results obtained from the node tests to identify the fault processors in the system is referred to as system-level diagnosis. Thus, diagnosis is exactly a process of discovering the system’s faulty nodes. The effective identification of faulty nodes is critical in reducing the chance of system breakdown and enhancing the stability of information transfer between nodes, which is greatly beneficial to the smoothness of the network system operation.
Ye et al. provided a five-round adaptive diagnostic algorithm in IEEE Transactions on Parallel and Distributed Systems in 2015. The algorithm could effectively diagnose the Hamiltonian networks and achieve an almost complete diagnosis. We implemented the Ye et al.’s algorithm into a computer program, and proceeded the five-round adaptive diagnostic program on some recursively constructed networks. In our experiments, the special case of the original algorithm being unable to completely diagnose is further analyzed. Moreover, in-depth analysis on the diagnostic capability of the network is also conducted in some recursively constructed networks by increasing the number of faulty nodes. In 2017, we experimented with hypercubes and obtained relevant analysis results. In this study, we analyzed the relevant results on crossed-cubes and exchanged hypercubes. We compared the performance through the five-round adaptive diagnostic program on these kinds of recursively constructed networks. We found that there is no significant difference in diagnosis ability of the hypercube and the crossed-cube. However, since the number of links of the exchanged hypercube is only about half that of the hypercube or the crossed-cube, the diagnosis ability of the exchanged hypercube is significantly worse than that of the hypercube and the cross cube.
32
Kuo, Che-nan, and 郭哲男. "A Study on Cycle and Path Embedding for Hypercubes and Folded Hypercubes." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/79830263232117113992.
Full textAbstract:
博士<br>國立成功大學<br>資訊工程學系碩博士班<br>97<br>Design of interconnection networks is an important integral part of the parallel processing or distributed system. There exists mutually con°icting requirements in designed and topology of interconnection networks. It becomes almost impossible for us to design a network which is optimum in all aspects. The hypercube has several excellent proper-
ties such as recursive structure, regularity, symmetry, small diameter, low degree, and much small edge complexity, which are very important for designing massively parallel
or distributed systems. Furthermore, one variant that has been the focus of great deal of research is the folded hypercube, which is an extension of the hypercube, constructed by adding an edge to every pair of nodes that are the farthest apart, i.e., two nodes with complementary addresses. The folded hypercube has been shown to be able to improve the system's performance over a regular hypercube in many measurements. Paths and cycles, which are two of the most fundamental networks for parallel and distributed computation, are suitable for designing simple algorithms with low commu-nication costs. Paths and cycles can also be used as control/data flow structures for
distributed computation in arbitrary networks. An application of paths to a practical problem was encountered in the on-line optimization of a complex flexible manufacturing system. These applications motivate us to embedding paths and cycles in networks.
In this dissertation, we consider fault-tolerant path or cycle embedding problems in hypercubes and in folded hypercubes.
33
Guo, Jyun-Hong, and 郭俊宏. "Pancyclicity of Hypercube Variants." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/91213389423540328808.
Full textAbstract:
碩士<br>大葉大學<br>資訊工程學系碩士班<br>96<br>Let G = (V, E) be a graph. For any two vertices x, y V, a cycle C is called (x,
y)-geodesic if there exists a shortest x-y path of G lies on C. A graph G is
weakly-geodesic r-pancyclic if for any two vertices x, y V, there exists a (x,
y)-geodesic of every length ranging from max{2d(x, y), r} to V. A graph G is
geodesic r-pancyclic if for any two vertices x, y V and any shortest x-y path P, there
exists a (x, y)-geodesic l-cycle containing P, where l is any integer between max{2d(x,
y), r} to Vinclusive. A bipartite graph G is weakly-geodesic (+r)-bipancyclic if for
any two vertices x, y V, there exists a (x, y)-geodesic cycle of every even length
ranging from 2d(x, y) + r to V. In this thesis, we shall show that the k-ary n-cube is
geodesic 3-pancyclic when k = 3, and weakly-geodesic (+2)-bipancyclic when k is
even.
For any two vertices x, y V, a cycle C is called (x, y)-balanced if the distance
dC(x, y) = max{dC(u, v) | u, v V} when G is not bipartite, and dC(x, y) = max{dC(u, v)
| x, u A, and y, v B} when G is bipartite with bipartitions A, B, and x A, y B. A
graph G is balanced r-pancyclic if for any two vertices x, y V, there exists a (x,
y)-balanced cycle of every length ranging from max{2d(x, y), r} to V. A graph G is
balanced (+r)-bipancyclic if for any two vertices x, y V, there exists a (x,
y)-balanced cycle of every even length ranging from 2d(x, y) + r to V. In this thesis,
we shall show that the k-ary n-cube is balanced 5-pancyclic when k = 3, and balanced
(+2)-bipancyclic when k>2 is even.
34
Chen, Chui-Cheng, and 陳垂呈. "Embedding Trees into Hypercubes." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/72813527393545665687.
Full textAbstract:
博士<br>國立交通大學<br>資訊工程研究所<br>84<br>The embedding problem has been widely discussed in recent
years. In this dissertation, we study embedding of various
guest graphs such as complete binary trees, incomplete binary
trees, tree machines and quadtrees into host graphs such as
hypercubes and incomplete hypercubes. We also study dynamic
reconfiguration of complete binary trees in faulty hypercubes.
First, we embed a complete binary tree into an incomplete
hypercube of the smallest size so that the adjacency of the
complete binary tree is preserved, and look for an incomplete
binary tree in a hypercube. Second, we optimally embed a large
complete binary tree into a hypercube of limited size. Third,
we embed a tree machine into an incomplete hypercube with
expansion 1, and embed a large tree machine into a hypercube of
limited size with load-balance. Fourth, we embed a quadtree
into a hypercube so that the adjacency of the quadtree is
preserved, and embed a quadtree into an incomplete hypercube
with expansion 1. Fifth, we dynamically reconfigure to embed a
complete binary tree into a faulty hypercube, and the number of
the affected nodes of the complete binary tree are as few as
possible after reconfiguring.
35
Hsiao, Ho-Lin, and 蕭鶴麟. "Folded Uni-Directional Hypercubes." Thesis, 1996. http://ndltd.ncl.edu.tw/handle/47199640615861274653.
Full textAbstract:
碩士<br>國立交通大學<br>資訊科學學系<br>84<br>We propose and analyze some variation of the uni-directional
interconnection network topology. The Foled Uni-directional
Hyperbues are new topologies obtainedby adding some extra links
from the uni-directional hyperbues(UHCs).We also derive the one
to one routing algorithms and analyze its average distanceby
computer. The diameter of these network topologies is better
than thatof UHC.Thus, a better structure is suggested for
applying to the Metropolitan Area Network(MANs).
36
WU, MING-LUN, and 吳明倫. "Network embedding on hypercubes." Thesis, 1992. http://ndltd.ncl.edu.tw/handle/27221324163523479154.
Full text
37
DU, HONG-CHANG, and 杜鴻昌. "Task allocation on hypercubes." Thesis, 1988. http://ndltd.ncl.edu.tw/handle/75717498630313681903.
Full text
38
吳瓔晃. "On Finding a Ring in an Injured Hypercube Using the Incomplete Hypercube Model." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/99726806198021648942.
Full textAbstract:
碩士<br>國立臺灣師範大學<br>資訊教育研究所<br>82<br>It is well known that the general problem of finding a Hamilton cycle (ring) in an arbitary graph is NP - complete. However, in an - dimensional hypercube, an advocated symmetric topological structure, the searching of a Hamilton cycle (ring) can be easily carried out in O (N), where N is the number of nodes in a complete hypercube. In an injured hypercube which has faulty nodes, the above O (N) algorithrn can't be applied for finding a ring in it. Hence, the purpose of our research is to develop a heuristic algorithm to find rings in the injured hypercubes. In this thesis, we develop a new incomplete hypercube model, which uses a subcbe - graph to present the topology of an injured hypercube, to provide a better representation for it. This incomplete hypercube model server as the foundation for our ring embeding algorithm. Our ring embedding algorthm employs depth - first search on subcube - graph associated with a heuristic break edge method to derive a ring passing through the maximal possible number of the available processor elements in the injured hypercube. Our method can provide a ring embedding on an injured hypercube with high processor utilization. Also, our method has no limitation on the number of faulty nodes that bothers many existing fault - tolerant ring embedding schemes. The time complexity of our method is O (mn), where m is the number of cube - nodes in a subcube - graph and n is the dimension of the injured hypercube.
39
"Optimal communication algorithms for hypercubes." Massachusetts Institute of Technology, Laboratory for Information and Decision Systems], 1989. http://hdl.handle.net/1721.1/3114.
Full textAbstract:
by D.P. Bertsekas ... [et al.].<br>Cover title.<br>Includes bibliographical references.<br>Supported by NSF with matching funds from Bellcore, Inc. ECS-8519058 ECS-8552419 Supported by the ARO. DAAL03-86-K-0171 Supported by the AFOSR. AFOSR-88-0032
40
Sheu, Shih-Hsien, and 許世憲. "Multicast Algorithms on Hypercube Multiprocessors." Thesis, 1995. http://ndltd.ncl.edu.tw/handle/56907282238435097056.
Full textAbstract:
碩士<br>國立中山大學<br>應用數學研究所<br>83<br>Multicast is highly demanded in many applications. Our efforts
in this thesis are to reduce the communication traffic of
multicast in hypercube multiprocessors. There are various
switching technologies, such as store-and-forward, circuit
switching, virtual cut-through and wormhole routing. Depending
on different switching technologies and evaluation criteria,
the multicast communication problem has been formulated as four
different graph theoretical problems, namely the Steiner tree
problem, the multicast tree problem, the multicast path problem
and the multicast cycle problem. In this thesis, we propose
three heuristic algorithms for the first three of the four
problems. Our multicast path algorithm is distributed, our
Steiner tree algorithm is centralized and our multicast tree
algorithm is hybrid. Compared with the previous results by
simulation, each of our heuristic algorithm improves the
communication traffic in the corresponding problem model.
41
Lin, Lieh-Yu, and 林冽佑. "Cycle Embedding in Folded Hypercubes." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/12813931349587015843.
Full textAbstract:
碩士<br>明新科技大學<br>資訊管理研究所<br>99<br>The cycle embedding problem in interconnection networks
is an important issue, because it is one of measurements for determining whether the topology of a network is suitable for an application in which embedding rings of various lengths into the topology is required. Embedding cycles of different sizes into a network are benefit to execute parallel programs efficiently. The folded hypercube is a popular network because of its attractive properties. Given an n-dimensional folded hypercube FQn and let e be any edge of FQn. In this paper, we discuss the number of simple k-cycles in FQn, which passing through the edge
e, for k = 4, 6.
42
Eu, Bo-Yan, and 游博元. "Non-isomorphic Paths in Hypercubes." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/76729293973210119169.
Full textAbstract:
碩士<br>國立新竹教育大學<br>應用數學系碩士班<br>100<br>Abstract
In this research we construct all non-isomorphic paths in the n-dimensional hypercube, and count the number of them. As the dimension n gets higher, the amount of the paths increases extremely large. So a normal algorithm cannot handle this situation. That is why we need to design a new method to construct and search non-isomorphic paths. This thesis offers an efficient algorithm to construct and search non-isomorphic paths. Two computer programs for solving the same problem are given here by using two different data structures. Both of them are programming by C.
43
Shih-Jung, Wu. "Fault-tolerant Simulation of a Class of Regular Graphs in Hypercubes and Incrementally Extensible Hypercubes." 2006. http://www.cetd.com.tw/ec/thesisdetail.aspx?etdun=U0002-0706200601030000.
Full text
44
Wu, Shih-Jung, and 武士戎. "Fault-tolerant Simulation of a Class of Regular Graphs in Hypercubes and Incrementally Extensible Hypercubes." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/68350016588012720764.
Full textAbstract:
博士<br>淡江大學<br>資訊工程學系博士班<br>94<br>The hypercube is a widely-used interconnection architecture in the parallel machine. The Incrementally Extensible Hypercube (IEH), which is derived from the hypercube, is a generalization of interconnection network. Unlike the hypercube, the IEH can be constructed for any number of nodes. In other words, the IEH is incrementally expandable. In this thesis, the problem of embedding and reconfiguring some regular structures is considered in an IEH with faulty nodes. In recent years, the Fibonacci cube is a new interconnection architecture derived from hypercube. It also has some properties differ from hypercube. Thus we discuss the embedding of Fibonacci cube into the faulty hypercube. Some fault-tolerant embedding algorithms are proposed in this thesis. First, the algorithm in the present study enables us to obtain the good embedding of a ring into a faulty IEH with 2-expansion. Such result can be tolerated up to (n+1) faults with congestion 1, load 1, and dilation 3. When we allow unbounded expansion, the result of embedding of a ring into a faulty IEH can be tolerated up to O(n*log2m) faults with congestion 1, load 1, and dilation 4. The embedding methods in the study are mainly optimized for balancing the processor loads, under the situation of minimizing dilation and congestion as far as possible. Next we consider embedding of mesh into faulty IEH. In 2-expansion, it can be tolerated (n+1) faults with dilation 3, congestion 1, and load 1. Moreover, it can be tolerated up to O(n2-(r+s)2) in unbounded expansion. We discuss embedding of a complete binary tree into faulty IEH in the third. The cost is dilation 4, congestion 1, and load 1. In 2-expansion and unbounded expansion, embedding of a complete binary tree into faulty IEH can be tolerated (n+1) and O(n2-h2) faults. Finally, embedding of Fibonacci cube into faulty hypercube with dilation 3, congestion 2, load 1, unbounded expansion and O(m2-n2) faults can be tolerated, induced by our algorithm.
45
Guo, Jiawei. "Tabu search heuristics for hypercube embedding." Thesis, 1992. http://spectrum.library.concordia.ca/4381/1/MM73691.pdf.
Full text
46
LIOU, YI-GANG, and 劉亦剛. "Five-round Adaptive Diagnosis on Hypercubes." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/st8q2q.
Full textAbstract:
碩士<br>明新科技大學<br>資訊管理系碩士班<br>105<br>The diagnosis of faulty nodes in large networks or multi-processor systems plays an extremely important role. The technique of using the test results obtained from the node tests to identify the fault processors in the system is referred to as system-level diagnosis. The failure of some nodes in large networks or multi-processor systems could lead to a breakdown of the entire network or system. Thus, diagnosis is exactly a process of discovering the system’s faulty nodes. The effective identification of faulty nodes is critical in reducing the adverse factors of the network architecture and enhancing the stability of information transfer between nodes, which is greatly beneficial to the smoothness of the network system operation.
Ye et al. provided a five-round adaptive diagnostic algorithm in IEEE Transactions on Parallel and Distributed Systems in 2015. The algorithm could effectively diagnose the Hamiltonian networks and achieve an almost complete diagnosis. The present study realizes the Ye et al.’s algorithm, where the special case of the original algorithm being able to completely diagnose is further analyzed. An in-depth analysis on the diagnostic capability of the network is also conducted in the 5-D and 6-D hypercubes by increasing the number of faulty nodes.
47
Hu, Wei-Jhun, and 胡偉諄. "2-Disjoint Geodesic Bipancyclicity of Hypercubes." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/57479496666186352093.
Full textAbstract:
碩士<br>大葉大學<br>資訊工程學系碩士班<br>97<br>Let G = (V, E) be a graph. For any two vertices u, v Î V(G), a cycle C is called (u,v)-geodesic if there exists a u-v shortest path of G lying on C. A bipartite graph G is called geodesic bipancyclic if for any two vertices u, v Î V, there exists a (u,v)-geodesic cycle of every even length ranging from max{2d(u, v), 4} to |V|. In this thesis, we first show that the hypercube Qn for n 4 is geodesic bipancyclic when it has two adjacent fault vertices. Then we prove that Qn is 2-disjoint geodesic bipancyclicity for n 4. That is, given any four vertices u, v, x, y without forming u, x, v, u, y, v, x, u, y, x, v, y paths, and given any even integers l1, l2 such that l1 + l2 2n, l1 min{2d(u, v) + 2, 2n}, and l2 min{2d(x, y) + 2, 2n}, there exist two disjoint cycles C1 and C2 in Qn such that C1 is a (u, v)-geodesic cycle of length l1, and C2 is a (x, y)-geodesic cycle of length l2.
48
Chen, Chia-Cheng, and 陳嘉振. "Bifanability of Bipartite Hypercube-like Networks." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/48609461565753669275.
Full textAbstract:
碩士<br>大葉大學<br>資訊工程學系碩士班<br>93<br>In this thesis, we introduce the concepts of bifanability and fault tolerant bifanability. We show that the n-dimensional hypercube Qn and bipartite hypercube-like Xn are f edges fault tolerant k*-bifanable for n ≥ 3, 0 ≤ f ≤ n - 2, 1 ≤ k ≤ n - f. We also prove that the n-dimensional hypercube Qn is f edges fault tolerant k*-bifanable with one faulty node for n ≥ 3, 0 ≤ f ≤ n - 3, k = n - f - 1.
49
Lin, Jen-Chih, and 林仁智. "Embedding Applications of Hypercube-Derived Computers." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/39104910597626924197.
Full textAbstract:
博士<br>淡江大學<br>資訊工程學系<br>88<br>In parallel computing, many parallel algorithms have been designed to solve different problems on various multiprocessor computers. The simulation of one architecture by another and the organization of computations in a network of processors are key issues to port software between multicomputer systems. The problem of simulating one network by another is modeled as a graph embedding problem where nodes and edges in the graph represent the processors and communication links between processors. Organizing computations in a network of processors is also modeled as a graph embedding. Therefore, graph embedding problems become the important applications in a wide variety of computational situations. Hypercube multiprocessors have recently offered a cost effective and feasible approach to supercomputing through parallelism at the processor level by directly connection a large number of low-cost processors with local memories, which communicate by message passing instead of, shared variables. There are some imperfections to be architecture for parallel computation, for example only 2n nodes that a hypercube can be produced. In order to conquer the difficulties associated with hypercubes, the Incrementally Extensible Hypercube (IEH) graph, the Supercube and the Flexible Hypercube have been proposed during past years. These architectures can be constructed for any number of nodes.
These methods of graph embedding of hypercube-derived computers have been proposed in this dissertation. First, we consider the problem of mapping a complete binary tree into a faulty Supercube or a Flexible Hypercube. Second, the Hamiltonian cycle of the Flexible Hypercube graph networks is investigated. The result can readily be used in optimal embedding of a linear array of processors (or a ring) in a faulty Flexible Hypercube. Third, we prove that there exists a Hamiltonian cycle in all of the IEH graphs, except those contains exactly 2n-1 nodes, where n is the dimension of the graph; an IEH graph, contains exactly 2n-1 nodes, only have a Hamiltonian path on it. The results enable us to obtain the well embedding of rings and linear array onto IEH graphs. Finally, we present a simple and efficient models to fulfill the embedding of full binary tree into an IEH graph containing 2n-1 nodes. Moreover, our embedding algorithm can be also applied into hypercubes with one faulty node.
50
Wang, Sheng-kai, and 王聖凱. "Edge-bipancyclicity of conditional faulty hypercubes." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/10130205784438624928.
Full textAbstract:
碩士<br>國立交通大學<br>資訊科學與工程研究所<br>94<br>Xu et al. showed that for any set of faulty edges F of an n-dimensional hypercube Qn with |F|≦n-1, each edge of Qn-F lies on a cycle of every even length from 6 to 2n, n≧4, provided not all edges in F are incident with the same vertex. In this paper, we find that under similar condition, the number of faulty edges can be much greater and the same result still holds. More precisely, we show that, for up to |F|=2n-5 faulty edges, each edge of the faulty hypercube Qn-F lies on a cycle of every even length from 6 to 2n with each vertex having at least two healthy edges adjacent to it, for n≧3. Moreover, this result is optimal in the sense that the result can not be guaranteed, if there are 2n-4 faulty edges.