Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 36 for “"linear ordering"”.
-
The Steiner Linear Ordering Problem: Application to resource-constrained scheduling problems
… which have the same priority. With the Steiner Linear Ordering problem, we can address systems where the elements involved have different levels of priority, either high or low. This allows us greater flexibility in modeling different resource-constrained scheduling problems. In this paper, we …
-
Map Folding
… then it is flat foldable, and the linear ordering of the faces is called a valid linear ordering. Otherwise, the map is unfoldable. In this thesis, we show that, given a linear ordering of the faces of an m × n map, we can decide in linear time whether it is a valid linear ordering …
-
Combinatorial optimization by stochastic evolution with applications to the physical design of VLSI circuits
… Partition, Hamilton Circuit, Traveling Salesman, Linear Ordering, Standard Cell Placement, and Multi-way Circuit Partitioning problems. It is empirically shown that SE out-performs the more established general optimization algorithm, namely, Simulated Annealing.
-
Updating the Vertex Separation of a Dynamically Changing Tree
… in the graph are arranged in the best possible linear ordering. Vertex separation was introduced by Lipton and Tarjan and has since been applied mainly in VLSI design. The tree is modified by either attaching another tree or removing a subtree. The first algorithm handles the special case when …
-
Lexicographic Products of Linear Orderings
For each pair of linear orderings (L, M), the representability number reprM(L) of L in M is the least ordinal alpha such that L can be order-embedded into the lexicographic power Malex . The case M = R is relevant to utility theory, a branch of mathematical economics. First we characterize …
-
Iterative approximation of Markov process parameters in a model of large scale business purchases
… failure, no movement, or advancement in a linear ordering of potential states terminating in a successful purchase. The transition probabilities which parameterize this model are determined via time series data of each salesman's progression in selling their products. In theory, the …
-
Settling Time Reducibility Orderings
It is known that orderings can be formed with settling time domination and strong settling time domination as relations on c.e. sets. However, it has been shown that no such ordering can be formed when considering computation time domination as a relation on $n$-c.e. sets where $n \geq 3$. This …
-
Weak orders, ordered partitions, and generalized weak orders
… and an asymmetric weak order R , have a natural linear ordering > . We show that there exists a one-to-one correspondence between complete weak orders, asymmetric weak orders and linearly ordered partitions of X . We enumerate the complete weak orders on an n-element set X by enumerating the …
-
Three Essays on Rationing, Matching and Scheduling
… successive units of good by following a linear ordering of individuals and non-zero demand pairs. The dual of a s.g.r. method is a standard of losses rationing (s.l.r.) method, it follows the same linear ordering to successively allocate units of deficit. In our main result, Theorem 1, we …
-
Dynamic algorithms for chordal and interval graphs
… and use it to decide whether there is a certain linear ordering of the graph's maximal cliques. This yields a fully dynamic algorithm to recognize interval graphs in O(n log n) time per edge insertion or deletion. The clique-separator graph may lead to dynamic algorithms for every proper subclass …
-
Pattern sequencing models in cutting stock problems
… The structure of this type of graphs admits a linear ordering of the vertices that de nes an ordering of the stacks, and consequently decides a sequence for the cutting patterns. The polytope de ned by this formulation is full-dimensional and the main inequalities in the model are proved to be …
-
Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation
… for the total weighted tardiness problem and linear ordering problem. By viewing moves from some known travelling salesman problem neighbourhoods as a combination of underlying moves, each reversing a section of the tour, greater insight into the structure of the neighbourhoods may be …
-
The double bind for non-traditional families in post-primary settings; to tell or not to tell their family identity
… and among teacher and student, as well as the linear ordering of intergenerational relations, such as teacher/student and adult/child are critiqued. Normalising discourses operate in practices such as notes home which presume two parents together. Teacher assumptions about heterosexual …
-
Lexicon and syntax in Korean phonology
… of Korean word-formation processes, the Stratum Ordering Hypothesis which maintains linear organization of lexical strata, is invalid, because it requires all conceivable combinations of loops. From the phonological aspect, violations of the Opacity Principle (Mohanan 1982) are unavoidable for …
-
Tight Representations of Specially-Structured 0-1 Linear, Quadratic, and Polynomial Programs
… Target Visitation Problem (TVP), the Quadratic Linear Ordering Problem (QLOP), and a special family of monomials of binary variables. For the first two efforts, which are known in the literature to be (mixed) 0-1 programs, we derive new families of valid inequalities that tighten existing forms …
-
Multilevel Methods for Sparsification and Linear Arrangement Problems on Networks
… schemes for multilevel algorithms developed for linear arrangement problems. Effectiveness of the set of coarse variables, and the corresponding interpolation matrix is the central problem in any multigrid algorithm. We are pushing the boundaries of fast maximum weighted matching algorithms for …
-
Automorphism Groups of Homogeneous Structures
… the pentagon graph, the random graph, and the linear ordering of the rationals. Countably infinite homogeneous structures are precisely the Fraisse limits of amalgamation classes of finitely generated structures. Homogeneous structures and their automorphism groups constitute the main theme of …
Page 1 of 2