By a planar tree is meant a realization of a tree in the plane, and by an isomorphism between two planar trees is meant a mapping which is not only an isomorphism in the usual sense of trees but which also preserves the clockwise cyclic order of edges about each node. Explicit formulae are given for each of the following: (1) the number of nonisomorphic unrooted planar trees with n edges, (2) the number of nonisomorphic rooted planar trees with n edges, and (3) the number of nonisomorphic...
Topics: DTIC Archive, Walkup, David W, BOEING SCIENTIFIC RESEARCH LABS SEATTLE WA MATHEMATICS RESEARCH LAB,...
Combinatorial experiments have led to the discovery that a nanophase alloy of Pt, Ru, Ni, and Zr is effective as an anode catalyst material for direct methanol fuel cells. This discovery has practical significance in that the electronic current densities achievable by use of this alloy are comparable or larger than those obtained by use of prior Pt/Ru catalyst alloys containing greater amounts of Pt. Heretofore, the high cost of Pt has impeded the commercialization of direct methanol fuel...
Topics: NASA Technical Reports Server (NTRS), FUEL CELLS, COMBINATORIAL ANALYSIS, COST REDUCTION, METHYL...
Contents: Feature extraction: a survey; Digital image processing for terrain pattern recognition; Multi-image clustering; The factors analysis technique applied to multi-spectral data; Mixture problems in pattern recognition; Analysis of geometrical moment features extracted from digitized tank photographs using an on line patter analysis and recognition system; A family of cubic spline subroutines; Pattern identification; The elementary concept of the Kalman filtering techniques;...
Topics: DTIC Archive, ARMY RESEARCH LAB RESEARCH TRIANGLE PARK NC ARMY RESEARCH OFFICE, *ARMY RESEARCH,...
8
8.0
Jul 30, 2019
07/19
by
British Combinatorial Conference (9th : 1983)
texts
eye 8
favorite 0
comment 0
p. cm. --
Topic: Combinatorial analysis -- Congresses
Source: removedNEL
The performed research demonstrates that important ligand classes can be synthesized on solid supports and can be used directly without purification to prepare asymmetric catalysts. For the catalyst system that was evaluated, the ligands prepared in parallel on support provided comparable enantioselectivities to purified ligands prepared individually over several steps in solution. Enantioselectivities greater than 90% ee were observed. These results hold promise for parallel synthesis and...
Topics: DTIC Archive, Ellman, Johnathan A., CALIFORNIA UNIV BERKELEY DEPT OF CHEMISTRY, *LIGANDS,...
The Final Technical Progress Report contains brief descriptions of published and to be published work. This work resulted in new knowledge concerning several areas of combinatorial mathematics including the aggregation of individual preferences via majority rule with an agenda, the determination of digraphs that arise in population ecology as domination graphs of tournaments representing the relation to prey on a collection of species, the determination of sub trees which are most central in a...
Topics: DTIC Archive, Reid, K B, CALIFORNIA STATE UNIV SAN MARCOS COLL OF ARTS AND SCIENCES, *TOPOLOGY,...
Given a grammar G and a string sigma, all possible parses of sigma can be constructed by repeatedly applying the rules of G in parallel. This process creates a 'lattice graph' in which any directed path from the least element to the greatest element is a sentential form that occurs in a (partial) parse of sigma. Examples are given illustrating how, at least for some grammars, this process does not lead to a combinatorial explosion, and could thus be used to parse strings very rapidly if...
Topics: DTIC Archive, Rosenfeld,Azriel, MARYLAND UNIV COLLEGE PARK COMPUTER VISION LAB, *COMPUTER LOGIC,...
Under conventional binary multiplication procedures an addition (or, equivalently, a subtraction) is performed for each non-zero digit of the multiplier or its absolute value, and the statistically expected number of additions per multiplication is one-half the number of these digits. This discussion develops Boolean functions for the recursive definition of substitute sets of multiplier digits for which the numbers of non-zeros are irreducible with statistically expected values very near...
Topics: DTIC Archive, Reitwiesner, George W, ARMY BALLISTIC RESEARCH LAB ABERDEEN PROVING GROUND MD,...
As part of our ONR sponsored research in the subtopic 'Linear-Time Stochastic Algorithms', we began investigating an optimization technique known as 'simulated annealing'. We have succeeded in giving a necessary and sufficient condition for the annealing algorithms to converge. New algorithms have been developed for open-loop computation of optimal state-dependent routine strategies for a fluid-approximation communication network model with a single destination. One of the algorithms is an...
Topics: DTIC Archive, Hajek,B, ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB, *ALGORITHMS,...
Given a grammar G and a string sigma, all possible parses of sigma can be constructed by repeatedly applying the rules of G in parallel. This process creates a 'lattice graph' in which any directed path from the least element to the greatest element is a sentential form that occurs in a (partial) parse of sigma. Examples are given illustrating how, at least for some grammars, this process does not lead to a combinatorial explosion, and could thus be used to parse strings very rapidly if...
Topics: DTIC Archive, Rosenfeld,Azriel, MARYLAND UNIV COLLEGE PARK COMPUTER VISION LAB, *COMPUTER LOGIC,...
This paper shows that a combination of dynamic programming gng and the classical meththod of successive approximations permits a systemattic study of various classes of combinatorial problems arising in scheduling theory, communication theory and network theory. Although the method cannot guarantee convergence to the actual solution, it furnishes a monotonic sequence of approximations by means of approximation in policy space. An important feature of the method is the use of the solution of...
Topics: DTIC Archive, RAND CORP SANTA MONICA CA, *CONTROL SYSTEMS, *DYNAMIC PROGRAMMING, *ITERATIONS,...
Due in considerable measure to its connection with linear programming, the combinatorial study of convex polytopes has progressed greatly in the past twenty-five years and many outstanding problems have been solved. However, the d-step conjecture, first formulated by W. M. Hirsch in 1957, remains unsettled. Both for its intrinsic interest and for its relationship to questions of computational complexity, it is probably the most important open problem on the combinatorial structure of polytopes....
Topics: DTIC Archive, Klee,Victor, WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS, *COMBINATORIAL ANALYSIS,...
The study of alpha-widths of (0, 1)-matrices (AD-274 181) continued, the emphasis being on those special classes of b by v (0, 1)-matrices having k 1's per row and 4 1's per column. It is assumed throughout that the class parameters b, v, k, r satisfy the inequality (b-r)(v-k-1) less than or equal to v - 1. Such a class has special combinatorial interest. For example, complements of finite projective planes and of Steiner triple systems have parameters satisfying this inequality. Several...
Topics: DTIC Archive, FULKERSON, D R, RAND CORP SANTA MONICA CA, *COMBINATORIAL ANALYSIS,...
An equivalent formulation for a standard linear programming problem was developed. For the case where the number of variables is twice the number of equations m, the equivalent problem has the same size but has the inverses of the first and second m columns of the matrix of coefficients.
Topics: DTIC Archive, RAND CORP SANTA MONICA CA, *LINEAR PROGRAMMING, COMBINATORIAL ANALYSIS, MATHEMATICAL...
A balanced incomplete block (BIB) design with b blocks is said to have the support size b* when exactly b* of the b blocks are distinct. BIB designs with b* b have interesting applications in design of experiments and controlled sampling. A method called trade off is introduced for the construction of BIB designs with repeated blocks. This method is utilized to study BIB designs with arbitrary v treatments is blocks of size k = 3 in general and with v = 7 and k = 3 in particular. It is shown...
Topics: DTIC Archive, Hedayat,A, ILLINOIS UNIV AT CHICAGO CIRCLE DEPT OF MATHEMATICS, *EXPERIMENTAL DESIGN,...
Combinatorial methods are used to derive the distribution of the busy period in a Markovian tandem queue and queues with finite capacity in five models each involving batches. (Author)
Topics: DTIC Archive, Mohanty,S G, STANFORD UNIV CA DEPT OF STATISTICS, *MATHEMATICAL MODELS, *QUEUEING...
72
72
Jul 30, 2019
07/19
by
Anderson, Ian, Ph. D
texts
eye 72
favorite 0
comment 0
xiii, 250 p. ; 24 cm
Topics: Combinatorial analysis, Set theory
We consider Newton's method for the linear fractional combinatorial optimization. First we show a strongly polynomial bound on the number of iterations for the general case. Then we consider the transshipment problem when the maximum arc cost is being minimized. This problem can be reduced to the maximum mean-weight cut problem, which is a special case of the linear fractional combinatorial optimization. We prove that Newton's method runs in O(m) iterations for the maximum mean weight cut...
Topics: DTIC Archive, Radzik, Thomas, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, *COMBINATORIAL ANALYSIS,...
A new modulation technique called combinatorial pulse position modulation (CPPM) is presented as a power-efficient alternative to quaternary pulse position modulation (QPPM) for direct-detection, free-space laser communications. The special case of 16C4PPM is compared to QPPM in terms of data throughput and bit error rate (BER) performance for similar laser power and pulse duty cycle requirements. The increased throughput from CPPM enables the use of forward error corrective (FEC) encoding for...
Topics: NASA Technical Reports Server (NTRS), BIT ERROR RATE, OPTICAL COMMUNICATION, POWER EFFICIENCY,...
Let G and G* be programs represented by directed graphs. We define a relation or = sub S, T between G and G* that formalizes the notion of G* simulating G with S-fold loss of space efficiency and T-fold loss of time efficiency, and prove that if G or = sub S, T G*, where G has n statements and G* is structured, then in the worst case T + log sub 2 (log sub 2 S) or = log sub 2 (n) + 0(log sub 2(log sub 2n)). (Author)
Topics: DTIC Archive, DeMillo,Richard A, GEORGIA INST OF TECH ATLANTA SCHOOL OF INFORMATION AND COMPUTER...
1
1.0
Jun 26, 2020
06/20
by
CPM (Symposium) (17th : 2006 : Barcelona, Spain)
texts
eye 1
favorite 0
comment 0
1 online resource (xii, 414 pages) :
Topics: Computer algorithms -- Congresses, Combinatorial analysis -- Congresses, Algorithmes -- Congrès,...
Topics: DTIC Archive, Rung, Bui T, NAVAL POSTGRADUATE SCHOOL MONTEREY CA, *CONTROL SYSTEMS,...
Systems analysis procedures are important for determining the proper allocation of information handling and decision making functions among the men in large man-machine organizations such as military command and control systems. Research is required for modeling and analyzing these functions and relating the sensitivities of these functions to the system criterion. This report presents the steps of a generalized systems analysis procedure for command and control systems. The steps are then...
Topics: DTIC Archive, Butz, A R, HONEYWELL INC MINNEAPOLIS MN, *MATHEMATICAL MODELS, *OPERATIONS RESEARCH,...
An experiment was conducted by means of a digital computer in which 54 human Ss were faced with the task of sampling from a hypothetical binomial universe in which a proportion, p, of all observations were 'top quality.' Ss sampled the universe sequentially, stopping after some number of observations had been made to make a terminal decision by selecting the one of the S's mutually exclusive and exhaustive subsets of the unit interval which S believed contained p. The four experimental...
Topics: DTIC Archive, NORTH CAROLINA UNIV AT CHAPEL HILL PSYCHOMETRIC LAB, *DECISION MAKING, BINOMIALS,...
9
9.0
Jul 24, 2018
07/18
by
CPM (Symposium) (13th : 2002 : Fukuoka-shi, Japan)
texts
eye 9
favorite 0
comment 0
viii, 288 pages : 24 cm
Topics: Computer algorithms -- Congresses, Combinatorial analysis -- Congresses, Combinatorial analysis,...
Topics: DTIC Archive, DANTZIG, GEORGE B, CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER, *LINEAR...
Let S sub 1, S sub 2, S sub M be a collection of subsets of a finite set S. The subset T of S is a partial transversal of size t of the subsets S sub 1, S sub 2, S sub M if (i) T consists of t elements of S, and (ii) the term rank of the incidence matrix of S sub 1, S sub 2, S sub M vs. elements of T is equal to t. Necessary and sufficient conditions in order that S sub 1, S sub 2, S sub M have mutually disjoint partial transversals T sub 1, T sub 2, T sub P of sizes t sub 1, t sub 2, t sub P...
Topics: DTIC Archive, RAND CORP SANTA MONICA CA, *COMBINATORIAL ANALYSIS, *MATRICES(MATHEMATICS),...
The problem of generating ordered trees was studied rather extensively in the recent literatures. As in all problems concerning the generation of a set of combinatorial objects, there are three major aspects of the problem. After defining a certain linear ordering over the set of combinatorial objects that we are interested in we need to: (1) design an algorithm for generating the combinatorial objects one by one, (2) design an algorithm for determining the rank (the relative position in the...
Topics: DTIC Archive, Liu, Chung Laung, ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE, *ARRAYS,...
The problem of generating ordered trees was studied rather extensively in the recent literatures. As in all problems concerning the generation of a set of combinatorial objects, there are three major aspects of the problem. After defining a certain linear ordering over the set of combinatorial objects that we are interested in we need to: (1) design an algorithm for generating the combinatorial objects one by one, (2) design an algorithm for determining the rank (the relative position in the...
Topics: DTIC Archive, Liu, Chung Laung, ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE, *ARRAYS,...
Research supported by NASA Langley Research Center includes many applications of aerospace design optimization and is conducted by teams of applied mathematicians and aerospace engineers. This paper investigates the benefits from this combined expertise in formulating and solving integer and combinatorial optimization problems. Applications range from the design of large space antennas to interior noise control. A typical problem, for example, seeks the optimal locations for vibration-damping...
Topics: NASA Technical Reports Server (NTRS), ENGINEERS, SCIENTISTS, AEROSPACE ENGINEERING, LINEAR...
Synthetic oligonucleotides and peptides have enjoyed a wide range of applications in both biology and chemistry. As a consequence, oligonucleotide-peptide conjugates have received considerable attention, most notably in the development of antisense constructs with improved pharmacological properties. In addition, oligonucleotide-peptide conjugates have been used as molecular tags, in the assembly of supramolecular arrays and in the construction of encoded combinatorial libraries. To make these...
Topics: NASA Technical Reports Server (NTRS), COMBINATORIAL ANALYSIS, CONJUGATES, PHARMACOLOGY, REACTION...
We study both analytically and numerically the complexity of the adiabatic quantum evolution algorithm applied to random instances of combinatorial optimization problems. We use as an example the NP-complete set partition problem and obtain an asymptotic expression for the minimal gap separating the ground and exited states of a system during the execution of the algorithm. We show that for computationally hard problem instances the size of the minimal gap scales exponentially with the problem...
Topics: NASA Technical Reports Server (NTRS), ALGORITHMS, COMBINATORIAL ANALYSIS, OPTIMIZATION, QUANTUM...
The research proposed in this document investigated multiobjective optimization approaches based upon the Genetic Algorithm (GA). Several versions of the GA have been adopted for multiobjective design, but, prior to this research, there had not been significant comparisons of the most popular strategies. The research effort first generalized the two-branch tournament genetic algorithm in to an N-branch genetic algorithm, then the N-branch GA was compared with a version of the popular...
Topics: NASA Technical Reports Server (NTRS), GENETIC ALGORITHMS, MULTIDISCIPLINARY DESIGN OPTIMIZATION,...
A method of rapid, programmable filtering of spectral transmittance, reflectance, or fluorescence data to measure the concentrations of chemical species has been proposed. By programmable is meant that a variety of spectral analyses can readily be performed and modified in software, firmware, and/or electronic hardware, without need to change optical filters or other optical hardware of the associated spectrometers. The method is intended to enable real-time identification of single or multiple...
Topics: NASA Technical Reports Server (NTRS), SPECTRUM ANALYSIS, SPECTRAL REFLECTANCE, COMBINATORIAL...
The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching...
Topics: DTIC Archive, Leighton,Tom, MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE, *GRIDS,...
Since October 1, 1979, research in Complexity Theory and Combinatorial Algorithms at the Department of Computer Science at the University of Illinois was supported by the Office of Naval Research. During this period of time, research work was carried out in the areas of Computational Complexity Theory, Scheduling Algorithms, Graph Algorithms, Dynamic Programming, and Fault- Tolerance Computing. We summarize here our accomplishments and our future plans, and we wish to request continued support...
Topics: DTIC Archive, Liu, C L, ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE, *ALGORITHMS,...
The problem of generating ordered trees was studied rather extensively in the recent literatures. As in all problems concerning the generation of a set of combinatorial objects, there are three major aspects of the problem. After defining a certain linear ordering over the set of combinatorial objects that we are interested in we need to (1) design an algorithm for listing the combinatorial objects one by one, (2) design an algorithm for determining the rank (the relative position in the linear...
Topics: DTIC Archive, Liu,Chung Laung, ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE, *ARRAYS,...
The problem of generating ordered trees was studied rather extensively in the recent literatures. As in all problems concerning the generation of a set of combinatorial objects, there are three major aspects of the problem. After defining a certain linear ordering over the set of combinatorial objects that we are interested in we need to (1) design an algorithm for listing the combinatorial objects one by one, (2) design an algorithm for determining the rank (the relative position in the linear...
Topics: DTIC Archive, Liu,Chung Laung, ILLINOIS UNIV AT URBANA DEPT OF COMPUTER SCIENCE, *ARRAYS,...
Given a grammar G and a string sigma, all possible parses of sigma can be constructed by repeatedly applying the rules of G in parallel. This process creates a 'lattice graph' in which any directed path from the least element to the greatest element is a sentential form that occurs in a (partial) parse of sigma. Examples are given illustrating how, at least for some grammars, this process does not lead to a combinatorial explosion, and could thus be used to parse strings very rapidly if...
Topics: DTIC Archive, Rosenfeld,Azriel, MARYLAND UNIV COLLEGE PARK COMPUTER VISION LAB, *COMPUTER LOGIC,...
A central limit theorem for empirical processes was proved. Applications to the electrical engineering problem of quantization and the statistical k-means clustering procedure were explored. (Author)
Topics: DTIC Archive, Pollard,David, YALE UNIV NEW HAVEN CONN DEPT OF STATISTICS, *QUANTIZATION,...
The catalog contains fractional factorial designs for use in experiments which investigate m factors at two levels and n factors at three levels. The grand mean mu, all main effects, and all two-factor interaction effects are estimated. All higher order interactions are assumed negligible and their absence allows estimation of the error variance. A design has been constructed for each of the 39 pairs (m,n) included from m+n=5 through m+5=10, (m, n not equal to zero). The design for (m,n) is...
Topics: DTIC Archive, Connor, W S, NATIONAL BUREAU OF STANDARDS GAITHERSBURG MD, *COMBINATORIAL ANALYSIS,...
The paper presents a method for treating multicommodity network flows in which limited resources are shared among several arcs instead of only one. The study extends the previous solution methods for networks with individual arc capacity constraints to cover joint constraints. This formulation can handle one or more joint capacity constraints in a multicommodity network; with some adjustment in the objective function, it can maximize a linear combination of commodity flows and find a feasible...
Topics: DTIC Archive, Wollmer, Richard D, RAND CORP SANTA MONICA CA, *LINEAR PROGRAMMING, *TRANSPORTATION,...
The output reliability of logic circuits can be increased by constructing them such that they are 'totally self-checking.' Totally self-checking circuits have their outputs encoded in an error-detecting code. By considering the modeling of potential hardware failures, circuit structure and output code, it is possible to construct circuits such that a failure within the circuit is indicated by a noncode output, and a code output indicates that the output is correct. This thesis discusses the...
Topics: DTIC Archive, Smith,James Edward, ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB,...
A good approximation is found to the number of non-separable sparsely edged labelled graphs, relevant in application in statistical mechanics. The enumeration of smooth labelled graphs, where we obtain an exact form for the exponential generating function, find the differential equation it satisfies and a combinatorial interpretation of this equation and finally study the sparsely edged case. We remark on a surprisingly close relationship between the results for the sparsely edged cases of the...
Topics: DTIC Archive, Wright,E M, ABERDEEN UNIV (SCOTLAND), *GRAPHS, *COMBINATORIAL ANALYSIS,...
An O(n sup 3) heuristic algorithm is described for solving n-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition. The algorithm involves as substeps the computation of a shortest spanning tree of the graph G defining the TSP, and the finding of a minimum cost perfect matching of a certain induced subgraph of G. A worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3/2....
Topics: DTIC Archive, Christofides, Nicos, CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH...
We discuss and solve the problem of constructing a diffeomorphic componentwise extension for an arbitrary invertible combinatorial function. Interpreted in physical terms, our solution constitutes a proof of the physical realizability of general computing mechanisms based on reversible primitives. (Author)
Topics: DTIC Archive, Toffoli,Tommaso, MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE,...
The problem of minimizing a multivariate function is recurrent in many disciplines as Physics, Mathematics, Engineering and, of course, Computer Science. Both deterministic and nondeterministic algorithms have been devised to perform this task. It is common practice to use the nondeterministic algorithms when the function to be minimized is not smooth or depends on binary variables, as in the case of combinatorial optimization. In this paper we describe a simple nondeterministic algorithm which...
Topics: DTIC Archive, Caprile, Bruno, MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB,...
This report documents two computer descriptions (COM-GEOM) of the M9 armored combat earthmover (ACE). This includes the standard and up armored versions of the vehicle. The appendices include the actual COM-GEOM listings of each of the descriptions. These descriptions are also available at the BRL either on cards or magnetic tape.
Topics: DTIC Archive, Shiells, James E, ARMY BALLISTIC RESEARCH LAB ABERDEEN PROVING GROUND MD, *ARMORED...
It is shown that any form of Search Rearrangement Backtracking (SRB) requires exponential time to verify the unsatisfiability of nearly all of a wide class of CNF boolean expressions. This result is based on an input model which generates n independant k-literal clauses from set of r boolean variables. We assume that k is fixed and n and r tend to infinity. The result holds if the limit as n approaches infinity of n/r(n) = lambda, is fixed and lambda1n(2)/(1-2 to the -K power). SRB requires...
Topics: DTIC Archive, Franco, John, INDIANA UNIV AT BLOOMINGTON DEPT OF COMPUTER SCIENCE, *BOOLEAN ALGEBRA,...
Partial Contents (Abstracts Only): New Developments in the Statistical Theory of Shape; Domains of Attraction for a Family of Processes Between Suprema and Sums; Ergodicity and Inequalities for Certain Point Processes; The Role of Poisson's Equation in Steady-State Simulation Output Analysis; Quick Simulations of Networks of GI/G/1 Queues; Prophet Inequalities and Related Problems of Optimal Stopping; Reaction-Diffusion Equations with Small Parameter: Probabilistic Approach; Stochastic Flow...
Topics: DTIC Archive, Iglehart, Donald L, STANFORD UNIV CA, *COMBINATORIAL ANALYSIS, *QUEUEING THEORY,...
