• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 5
  • Tagged with
  • 5
  • 5
  • 3
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Local Prime Factor Decomposition of Approximate Strong Product Graphs

Hellmuth, Marc 07 July 2010 (has links) (PDF)
In practice, graphs often occur as perturbed product structures, so-called approximate graph products. The practical application of the well-known prime factorization algorithms is therefore limited, since most graphs are prime, although they can have a product-like structure. This work is concerned with the strong graph product. Since strong product graphs G contain subgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to develop local approaches that cover a graph by factorizable patches and then use this information to derive the global factors. First, we investigate the local structure of strong product graphs and introduce the backbone B(G) of a graph G and the so-called S1-condition. Both concepts play a central role for determining the prime factors of a strong product graph in a unique way. Then, we discuss several graph classes, in detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear time prime factorization algorithms. Combining these results, we then derive a new local prime factorization algorithm for all graphs. Finally, we discuss approximate graph products. We use the new local factorization algorithm to derive a method for the recognition of approximate graph products. Furthermore, we evaluate the performance of this algorithm on a sample of approximate graph products.
2

A Prime Factor Theorem for a Generalized Direct Product

Imrich, Wilfried, Stadler, Peter F. 05 February 2019 (has links)
We introduce the concept of neighborhood systems as a generalization of directed, reflexive graphs and show that the prime factorization of neighborhood systems with respect to the the direct product is unique under the condition that they satisfy an appropriate notion of thinness.
3

Distributed System for Factorisation of Large Numbers

Johansson, Angela January 2004 (has links)
<p>This thesis aims at implementing methods for factorisation of large numbers. Seeing that there is no deterministic algorithm for finding the prime factors of a given number, the task proves rather difficult. Luckily, there have been developed some effective probabilistic methods since the invention of the computer so that it is now possible to factor numbers having about 200 decimal digits. This however consumes a large amount of resources and therefore, virtually all new factorisations are achieved using the combined power of many computers in a distributed system. </p><p>The nature of the distributed system can vary. The original goal of the thesis was to develop a client/server system that allows clients to carry out a portion of the overall computations and submit the result to the server. </p><p>Methods for factorisation discussed for implementation in the thesis are: the quadratic sieve, the number field sieve and the elliptic curve method. Actually implemented was only a variant of the quadratic sieve: the multiple polynomial quadratic sieve (MPQS).</p>
4

Local Prime Factor Decomposition of Approximate Strong Product Graphs: Local Prime Factor Decompositionof Approximate Strong Product Graphs

Hellmuth, Marc 22 April 2010 (has links)
In practice, graphs often occur as perturbed product structures, so-called approximate graph products. The practical application of the well-known prime factorization algorithms is therefore limited, since most graphs are prime, although they can have a product-like structure. This work is concerned with the strong graph product. Since strong product graphs G contain subgraphs that are itself products of subgraphs of the underlying factors of G, we follow the idea to develop local approaches that cover a graph by factorizable patches and then use this information to derive the global factors. First, we investigate the local structure of strong product graphs and introduce the backbone B(G) of a graph G and the so-called S1-condition. Both concepts play a central role for determining the prime factors of a strong product graph in a unique way. Then, we discuss several graph classes, in detail, NICE, CHIC and locally unrefined graphs. For each class we construct local, quasi-linear time prime factorization algorithms. Combining these results, we then derive a new local prime factorization algorithm for all graphs. Finally, we discuss approximate graph products. We use the new local factorization algorithm to derive a method for the recognition of approximate graph products. Furthermore, we evaluate the performance of this algorithm on a sample of approximate graph products.
5

Distributed System for Factorisation of Large Numbers

Johansson, Angela January 2004 (has links)
This thesis aims at implementing methods for factorisation of large numbers. Seeing that there is no deterministic algorithm for finding the prime factors of a given number, the task proves rather difficult. Luckily, there have been developed some effective probabilistic methods since the invention of the computer so that it is now possible to factor numbers having about 200 decimal digits. This however consumes a large amount of resources and therefore, virtually all new factorisations are achieved using the combined power of many computers in a distributed system. The nature of the distributed system can vary. The original goal of the thesis was to develop a client/server system that allows clients to carry out a portion of the overall computations and submit the result to the server. Methods for factorisation discussed for implementation in the thesis are: the quadratic sieve, the number field sieve and the elliptic curve method. Actually implemented was only a variant of the quadratic sieve: the multiple polynomial quadratic sieve (MPQS).

Page generated in 0.0654 seconds