Spelling suggestions: "subject:"combinatorial analysis"" "subject:"ombinatorial analysis""
31 
Classification and enumeration of finite semigroups /Distler, Andreas. January 2010 (has links)
Thesis (Ph.D.)  University of St Andrews, June 2010.

32 
Bottleneck problems in combinatorics and optimization /Leung, Pakkin, Richard, January 1998 (has links)
Thesis (M. Phil.)University of Hong Kong, 1999.

33 
Aspects of signed and minus domination in graphsUngerer, Elna 27 August 2012 (has links)
Ph.D. / In Chapter 1 we will give a brief historical account of domination theory and define the necessary concepts which we use in the remainder of the thesis. In Chapter 2 we establish a lower bound for the minus ksubdomination number of trees and characterize those trees which achieve this lower bound. We also compute the value of Yks101 for comets and for cycles. We then show that the decision problem corresponding to the computation of Yks101 is NPcomplete, even for bipartite graphs. In Chapter 3 we characterize those trees T which achieve the lower bound of Cockayne and Mynhardt, thus generalizing the results of [11] and [2]. We also compute Yks11 for comets and cycles. In Chapter 4 we study the partial signed domination number of a graph. In particular, we establish a lower bound on Yc/d for regular graphs and prove that the decision problem corresponding to the computation of the partial signed domination number is NPcomplete. Chapter 5 features the minus bondage number b (G) of a nonempty graph G, which is defined as the minimum cardinality of a set of edges whose removal increases the minus domination number of G. We show that the minus bondage and ordinary bondage numbers of a graph are incomparable. Exact values for certain well known classes of graphs are computed and an upper bound for b is given for trees. Finally, we show that the decision problem corresponding to the computation of b is N P  hard, even for bipartite graphs. We conclude, in Chapter 6, by discussing possible directions for future research.

34 
Domination in graphs with bounded degreesDorfling, Samantha 10 September 2012 (has links)
M.Sc. / Let G be a graph and D a set of vertices such that every vertex in G is in D or adjacent to at least one vertex in D. Then D is called a dominating set of G and the smallest cardinality of such a dominating set of G is known as the domination number of G, denoted by y(G). This short dissertation is a study of the domination number in graphs with bounds on both the minimum and maximum degrees. In Chapter 1 we give all definitions, terminology and references related to the material presented in this thesis. In Chapter 2 we study an article by McCuaig and Shepherd which considers graphs with minimum degree two and gives an upper bound for their domination numbers in terms of their order. This bound is also an improvement of one originally determined by Ore. In Chapter 3 an article by Fisher, Fraughnaugh and Seager is studied. Here the domination number in graphs with maximum degree at most three is discussed. Furthermore au upper bound on the domination number of a graph is given in terms of its order, size and the number of isolated vertices it contains. This result is an extension of a previous result by Reed on domination in graphs with minimum degree three. A set U of vertices of a graph G = (V, E) is kdominating if each vertex of V — U is adjacent to at least k vertices of U. The kdomination number of G, Yk (G), is the smallest cardinality of a kdominating set of G. Finally in Chapter 4 we study an article by Cockayne, Gamble and Shepherd which gives an upper bound for the kdomination number of a graph with minimum degree at least k. This result is a generalization of a result by Ore.

35 
Polyhedral studies on scheduling and routing problemsWang, Yaoguang January 1991 (has links)
During the last decade, there have been major advances in solving a class of largescale real world combinatorial optimization problems. Such problems are formulated as Travelling Salesman Problems (TSP), some involving up to thousands of cities. These achievements, mainly due to the use of so called polyhedral techniques, have established the importance of the polyhedral study for various combinatorial optimization problems.
This thesis studies polyhedral structures of two well known combinatorial problems: (i) precedence constrained single machine scheduling and (ii) TSP, both Symmetric TSP (STSP) and Asymmetric TSP (ATSP). These problems are of both theoretical interest and practical importance. Better knowledge of the polyhedral descriptions of these problems may facilitate the polyhedral study of more complex scheduling and routing problems.
For the scheduling problem, we present two classes of facetial inequalities, which suffice to describe the linear system of the scheduling problem when the precedence constraints are seriesparallel. We also propose a cutting plane procedure based on these facet cuts. The computational results show the procedure yields feasible schedules with relative deviations from the optimum less than 0.25% on the average and less than 1% in the empirical worst case.
For TSPs, we explore a Hamiltonian path approach to the polyhedral study. We propose various facet extension techniques for deriving large classes of facets from known facets. In the STSP case, we propose new clique lifting results. In the ATSP case, we develop a Tree Composition method, which generates all nonspanning clique tree facetial inequalities. / Business, Sauder School of / Graduate

36 
Topics in combinatorial analysisUnknown Date (has links)
"This paper is concerned with systems of distinct representatives (abbreviated by S.D.R.) and related combinatorial topics"Introduction. / Typescript. / "August, 1959." / "Submitted to the Graduate Council of Florida State University in partial fulfillment of the requirements for the degree of Master of Science." / Advisor: Marion F. Tinsley, Professor Directing Paper. / Includes bibliographical references (leaf 25).

37 
Fundamentals of Partially Ordered SetsCompton, Lewis W. 08 1900 (has links)
Gives the basic definitions and theorems of similar partially ordered sets; studies finite partially ordered sets, including the problem of combinatorial analysis; and includes the ideas of complete, dense, and continuous partially ordered sets, including proofs.

38 
Jump numbers, hyperrectangles and Carlitz compositionsCheng, Bo January 1999 (has links)
Thesis (Ph.D.)University of the Witwatersrand, Faculty of Science, 1998. / A thesis submitted to the Faculty of Science, University of the Witwatersrand,
Johannesburg, in fulfilment of the requirements for the degree of
Doctor of Philosophy.
Johannesburg 1998 / Let A = (aij) be an m x n matrix. There is a natural way to associate a
poset PA with A. A jump in a linear extension of PA is a pair of consecutive
elements which are incomparable in Pa. The jump number of A is the minimum
number of jumps in any linear extension of PA. The maximum jump
number over a class of n x n matrices of zeros and ones with constant row and
column sum k, M (n, k), has been investigated in Chapter 2 and 3. Chapter
2 deals with extremization problems concerning M (n ,k). In Chapter 3, we
obtain the exact values for M (11,k). M(n,Q), M (n,n3) and M(n,n4).
The concept of frequency hyperrectangle generalizes the concept of latin
square. In Chapter 4 we derive a bound for the maximum number of mutually
orthogonal frequency hyperrectangles. Chapter 5 gives two algorithms to
construct mutually orthogonal frequency hyperrectangles.
Chapter 6 is devoted to some enumerative results about Carlitz compositions
(compositions with different adjacent parts).

39 
Arithmetic properties of overpartition functions with combinatorial explorations of partition inequalities and partition configurationsAlanazi, Abdulaziz Mohammed January 2017 (has links)
A thesis submitted to the Faculty of Science, University of the
Witwatersrand, Johannesburg, in ful lment of the requirements for
the degree of Doctor of Philosophy.
Johannesburg, 2017. / In this thesis, various partition functions with respect to `regular overpartitions, a
special partition inequality and partition con gurations are studied.
We explore new combinatorial properties of overpartitions which are natural generalizations
of integer partitions. Building on recent work, we state general combinatorial
identities between standard partition, overpartition and `regular partition
functions. We provide both generating function and bijective proofs.
We then establish an in nite set of Ramanujantype congruences for the `regular
overpartitions. This signi cantly extends the recent work of Shen which focused
solely on 3{regular overpartitions and 4{regular overpartitions. We also prove some
of the congruences for `regular overpartition functions combinatorially.
We then provide a combinatorial proof of the inequality p(a)p(b) > p(a+b), where
p(n) is the partition function and a; b are positive integers satisfying a+b > 9, a > 1
and b > 1. This problem was posed by Bessenrodt and Ono who used the inequality
to study a maximal multiplicative property of an extended partition function.
Finally, we consider partition con gurations introduced recently by Andrews and
Deutsch in connection with the StanleyElder theorems. Using a variation of Stanley's
original technique, we give a combinatorial proof of the equality of the number
of times an integer k appears in all partitions and the number of partition con
gurations of length k. Then we establish new generalizations of the Elder and
con guration theorems. We also consider a related result asserting the equality
of the number of 2k's in partitions and the number of unrepeated multiples of k,
providing a new proof and a generalization. / MT2017

40 
Techniques in Lattice Basis ReductionUnknown Date (has links)
The mathematical theory of nding a basis of shortest possible vectors in a
given lattice L is known as reduction theory and goes back to the work of Lagrange,
Gauss, Hermite, Korkin, Zolotarev, and Minkowski. Modern reduction theory is voluminous
and includes the work of A. Lenstra, H. Lenstra and L. Lovasz who created
the well known LLL algorithm, and many other researchers such as L. Babai and C. P.
Schnorr who created signi cant new variants of basis reduction algorithms. The shortest
vector (SVP) and closest vector (CVP) problems, presently considered intractable,
are algorithmic tasks that lie at the core of many number theoretic problems, integer
programming, nding irreducible factors of polynomials, minimal polynomials of algebraic
numbers, and simultaneous diophantine approximation. Lattice basis reduction
also has deep and extensive connections with modern cryptography, and cryptanalysis
particularly in the postquantum era. In this dissertation we study and compare
current systems LLL and BKZ, and point out their strengths and drawbacks. In
addition, we propose and investigate the e cacy of new optimization techniques, to
be used along with LLL, such as hill climbing, random walks in groups, our lattice
di usionsub lattice fusion, and multistage hybrid LDSFHC technique. The rst two methods rely on the sensitivity of LLL to permutations of the
input basis B, and optimization ideas over the symmetric group Sm viewed as a
metric space. The third technique relies on partitioning the lattice into sublattices,
performing basis reduction in the partition sublattice blocks, fusing the sublattices,
and repeating. We also point out places where parallel computation can reduce runtimes
achieving almost linear speedup. The multistage hybrid technique relies on the
lattice di usion and sublattice fusion and hill climbing algorithms. Unlike traditional
methods, our approach brings in better results in terms of basis reduction towards
nding shortest vectors and minimal weight bases. Using these techniques we have
published the competitive lattice vectors of ideal lattice challenge on the lattice hall of
fame. Toward the end of the dissertation we also discuss applications to the multidimensional
knapsack problem that resulted in the discovery of new large sets of
geometric designs still considered very rare. The research introduces innovative techniques
in lattice basis reduction theory and provides some space for future researchers
to contemplate lattices from a new viewpoint. / Includes bibliography. / Dissertation (Ph.D.)Florida Atlantic University, 2016. / FAU Electronic Theses and Dissertations Collection

Page generated in 0.089 seconds