The main results of this dissertation are various algorithms related to partially ordered sets. The dissertation basically consists of two parts. The first part treats algorithms that generate ideals of partially ordered sets. The second part concerns the generation of partially ordered sets themselves. First, we present two algorithms for listing ideals of a forest poset. These algorithms generate ideals in a Gray Code manner, that is, consecutive ideals differ by exactly one element. Both algorithms use storage O(n), where n is the number of elements in the poset. The first algorithm traverses, at each phase, the current ideal being listed and runs in time O(nN), where N is the number of ideals of the poset. The second algorithm mimics the first but eliminates the traversal and runs in time O(N). This algorithm has the property that the amount of computation between successive ideals is O(1). Secondly, we give orderly algorithms for constructing acyclic digraphs, acyclic transitive digraphs, finite topologies and finite topologies and finite lattices. For the first time we show that the number of finite lattices on 11, 12, and 13 elements are 37622, 262775, and 2018442, respectively, and the number of finite topologies on 8 and 9 elements are 35979 and 363083, respectively. We also describe orderly algorithms for generating k-colored graphs. We present, in particular, an algorithm for generating connected bicolorable graphs. We also prove some properties of a canonic matrix which might be generally useful for improving the efficiency of orderly algorithms. / Graduate

No description available.

This thesis is concerned with the analysis of a Rectilinear Distance Location Allocation Problem, where the costs are directly proportional to rectilinear distances and the amount shipped. The problem is formulated as a Mixed Integer Bilinear Programming Problem and as a Discrete Location Allocation Problem. Using linear programming relaxations constructed via the Reformulation-Linearization Technique (RLT), the latter formulation is shown to provide stronger lower bounds and is therefore adopted for implementation. In addition, cutting planes are developed to further strengthen the linear programming relaxation. The special structure of the resulting linear program is exploited in order to get a quick lower bound via a suitable Lagrangian dual formulation. This lower bounding scheme is embedded within a finitely convergent Branch and Bound algorithm that enumerates over the location decision variable space. An illustrative example and computational experience are provided to demonstrate the efficacy of the proposed algorithm. / Master of Science

This work presents a numerical investigation of self-avoiding walks (SAWs) on percolation clusters, a canonical model for polymers in disordered media. A new algorithm has been developed allowing exact enumeration of over ten thousand steps. This is an increase of several orders of magnitude compared to previously existing enumeration methods, which allow for barely more than forty steps. Such an increase is achieved by exploiting the fractal structure of critical percolation clusters: they are hierarchically organized into a tree of loosely connected nested regions in which the walks segments are enumerated separately. After the enumeration process, a region is \"decimated\" and behaves in the following effectively as a single point. Since this method only works efficiently near the percolation threshold, a chain-growth Monte Carlo algorithm has also been used. Main focus of the investigations was the asymptotic scaling behavior of the average end-to-end distance as function of the number of steps on critical clusters in different dimensions. Thanks the highly efficient new method, existing estimates of the scaling exponents could be improved substantially. Also investigated were the number of possible chain conformation and the average entropy, which were found to follow an unusual scaling behavior. For concentrations above the percolation threshold the exponent describing the growth of the end-to-end distance turned out to differ from that on regular lattices, defying the prediction of the accepted theory. Finally, SAWs with short range attractions on percolation clusters are discussed. Here, it emerged that there seems to be no temperature-driven collapse transition as the asymptotic scaling behavior of the end-to-end distance even at zero temperature is the same as for athermal SAWs. / Die vorliegenden Arbeit präsentiert eine numerische Studie von selbstvermeidenden Zufallswegen (SAWs) auf Perkolationsclustern, ein kanonisches Modell für Polymere in stark ungeordneten Medien. Hierfür wurde ein neuer Algorithmus entwickelt, welcher es ermöglicht SAWs von mehr als zehntausend Schritten exakt auszuzählen. Dies bedeutet eine Steigerung von mehreren Größenordnungen gegenüber der zuvor existierenden Methode, welche kaum mehr als vierzig Schritte zulässt. Solch eine Steigerung wird erreicht, indem die fraktale Struktur der Perkolationscluster geziehlt ausgenutzt wird: Die Cluster werden hierarchisch in lose verbundene Gebiete unterteilt, innerhalb welcher Wegstücke separat ausgezählt werden können. Nach dem Auszählen wird ein Gebiet \"dezimiert\" und verhält sich während der Behandlung größerer Gebiete effektiv wie ein Gitterpunkt. Da diese neue Methode nur nahe der Perkolationsschwelle funktioniert, wurde zum Erzielen der Ergebnisse zudem ein Kettenwachstums-Monte-Carlo-Algorithmus (PERM) eingesetzt. Untersucht wurde zunächst das asymptotische Skalenverhalten des Abstands der beiden Kettenenden als Funktion der Schrittzahl auf kritischen Clustern in verschiedenen Dimensionen. Dank der neuen hochperformanten Methode konnten die bisherigen Schätzer für den dies beschreibenden Exponenten signifikant verbessert werden. Neben dem Abstand wurde zudem die Anzahl der möglichen Konformationen und die mittlere Entropie angeschaut, für welche ein ungewöhnliches Skalenverhalten gefunden wurde. Für Konzentrationen oberhalb der Perkolationsschwelle wurde festgestellt, dass der Exponent, welcher das Wachstum des Endabstands beschreibt, nicht dem für freie SAWs entspricht, was nach gängiger Lehrmeinung der Fall sein sollte. Schlussendlich wurden SAWs mit Anziehung zwischen benachbarten Monomeren untersucht. Hier zeigte sich, dass es auf kritischen Perkolationsclustern keinen Phasenübergang zu geben scheint, an welchem die Ketten kollabieren, sondern dass das Skalenverhalten des Endabstands selbst am absoluten Nullpunkt der Temperatur unverändert ist.

An isohedral tiling is a tiling of congruent polygons that are also transitive, which is to say the configuration of degrees of vertices around each face is identical. Regular tessellations, or tilings of congruent regular polygons, are a special case of isohedral tilings. Viewing these tilings as graphs in planes, both Euclidean and non-Euclidean, it is possible to pose various problems of enumeration on the respective graphs. In this paper, we investigate some near-regular isohedral tilings of triangles and quadrilaterals in the hyperbolic plane. For these tilings we enumerate vertices as classified by number of edges in the shortest path to a given origin, by combinatorially deriving their respective generating functions.

We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the formal power series generating function of the number of interval graphs on n vertices has a positive radius of convergence. We have found that it is zero. We have obtained a lower bound and an upper bound on the number of interval graphs on n vertices. We also study the application of interval graphs to the dynamic storage allocation problem. Dynamic storage allocation has been shown to be NP-complete by Stockmeyer. Coloring interval graphs on-line has applications to dynamic storage allocation. The most colors used by Kierstead's algorithm is 3 ω -2, where ω is the size of the largest clique in the graph. We determine a lower bound on the colors used. One such lower bound is 2 ω -1.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23548号 / 情博第778号 / 新制||情||132(附属図書館) / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 湊 真一, 教授 山本 章博, 准教授 川原 純 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

A map is an embedding of the vertices and edges of a graph into a compact 2-manifold such that the remainder of the surface has components homeomorphic to open disks. With the goal of proving the Four Colour Theorem, Tutte began the field of map enumeration in the 1960's. His methods included developing the edge deletion decomposition, developing and solving a recurrence and functional equation based on this decomposition, and developing the medial bijection between two equinumerous infinite families of maps. Beginning in the 1980's Jackson, Goulden and Visentin applied algebraic methods in enumeration of non-planar and non-orientable maps, to obtain results of interest for mathematical physics and algebraic geometry, and the Quadrangulation Conjecture and the Map-Jack Conjecture. A special case of the former is solved by Tutte's medial bijection. The latter uses Jack symmetric functions which are a topic of active research. In the 1960's Walsh and Lehman introduced a method of encoding orientable maps. We develop a similar method, based on depth first search and extended to non-orientable maps. With this, we develop a bijection that extends Tutte's medial bijection and partially solves the Quadrangulation Conjecture. Walsh extended Tutte's recurrence for planar maps to a recurrence for all orientable maps. We further extend the recurrence to include non-orientable maps, and express it as a partial differential equation satisfied by the generating series. By appropriately interpolating the differential equation and applying the depth first search method, we construct a parameter that empirically fulfils the conditions of the Map-Jack Conjecture, and we prove some of its predicted properties. Arques and Beraud recently obtained a continued fraction form of a specialisation of the generating series for maps. We apply the depth search method with an ordinary differential equation, to construct a bijection whose existence is implied by the continued fraction.

CTCs have emerged as a potential source of clinical significance. But with numerous isolating systems currently available, the numbers of captured CTCs vary widely. At this point, CellSearch remains the only FDA-approved system with clinical significance whereby the results could be used to monitor patients with metastatic colon, breast, or prostate cancer. However, its inability to isolate CTCs from non-high risk prostate cancer patients or CTCs that are EpCAM-negative has led to criticism. In this study, we have shown that size-based filtration successfully isolates CTCs from patients with localized and metastatic prostate cancer. We have also shown that CTCs can be successfully isolated from low and intermediate risk groups. Additionally, clusters of CTCs were preserved and isolated in all localized risk groups and metastatic patients. Furthermore, we enumerated the isolated CTCs using automated and manual methods in low risk, intermediate risk, high risk, and metastatic prostate cancer. The automated and manual counts were comparable. Moreover, the amounts of clusters and the size of clusters correlated with the status and stage of prostate cancer. / October 2016

Counting lattice paths where the number of occurrences of a given pattern is monitored requires a careful analysis of the pattern. Not the length, but the characteristics of the pattern are responsible for the difficulties in finding explicit solutions. Certain features, like overlap and difference in number of ! and " steps determine the recursion formula. In the case of ballot paths, that is paths the stay weakly above the line y = x, the solutions to the recursions are typically polynomial sequences. The objects of Finite Operator Calculus are polynomial sequences, thus the theory can be used to solve the recursions. The theory of Finite Operator Calculus is strengthened and extended to the multivariate setting in order to obtain solutions, and to prepare for future applications. / by Shaun Sullivan. / Thesis (Ph.D.)--Florida Atlantic University, 2011. / Includes bibliography. / Electronic reproduction. Boca Raton, Fla., 2011. Mode of access: World Wide Web.